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