bits.h 1019 Bytes
Newer Older
gejun's avatar
gejun committed
1 2 3 4 5 6
// Copyright (c) 2009 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// This file defines some bit utilities.

7 8
#ifndef BUTIL_BITS_H_
#define BUTIL_BITS_H_
gejun's avatar
gejun committed
9

10 11
#include "butil/basictypes.h"
#include "butil/logging.h"
gejun's avatar
gejun committed
12

13
namespace butil {
gejun's avatar
gejun committed
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
namespace bits {

// Returns the integer i such as 2^i <= n < 2^(i+1)
inline int Log2Floor(uint32_t n) {
  if (n == 0)
    return -1;
  int log = 0;
  uint32_t value = n;
  for (int i = 4; i >= 0; --i) {
    int shift = (1 << i);
    uint32_t x = value >> shift;
    if (x != 0) {
      value = x;
      log += shift;
    }
  }
  DCHECK_EQ(value, 1u);
  return log;
}

// Returns the integer i such as 2^(i-1) < n <= 2^i
inline int Log2Ceiling(uint32_t n) {
  if (n == 0) {
    return -1;
  } else {
    // Log2Floor returns -1 for 0, so the following works correctly for n=1.
    return 1 + Log2Floor(n - 1);
  }
}

}  // namespace bits
45
}  // namespace butil
gejun's avatar
gejun committed
46

47
#endif  // BUTIL_BITS_H_