base/bits.h

   1 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // This file defines some bit utilities.
   6
   7 #ifndef BASE_BITS_H_
   8 #define BASE_BITS_H_
   9 #pragma once
  10
  11 #include "base/basictypes.h"
  12 #include "base/logging.h"
  13
  14 namespace base {
  15 namespace bits {
  16
  17 // Returns the integer i such as 2^i <= n < 2^(i+1)
  18 inline int Log2Floor(uint32 n) {
  19   if (n == 0)
  20     return -1;
  21   int log = 0;
  22   uint32 value = n;
  23   for (int i = 4; i >= 0; --i) {
  24     int shift = (1 << i);
  25     uint32 x = value >> shift;
  26     if (x != 0) {
  27       value = x;
  28       log += shift;
  29     }
  30   }
  31   DCHECK_EQ(value, 1u);
  32   return log;
  33 }
  34
  35 // Returns the integer i such as 2^(i-1) < n <= 2^i
  36 inline int Log2Ceiling(uint32 n) {
  37   if (n == 0) {
  38     return -1;
  39   } else {
  40     // Log2Floor returns -1 for 0, so the following works correctly for n=1.
  41     return 1 + Log2Floor(n - 1);
  42   }
  43 }
  44
  45 }  // namespace bits
  46 }  // namespace base
  47
  48 #endif  // BASE_BITS_H_