bits.h revision 5821806d5e7f356e8fa4b058a389a808ea183019
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file defines some bit utilities. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef BASE_BITS_H_ 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BASE_BITS_H_ 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace bits { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the integer i such as 2^i <= n < 2^(i+1) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int Log2Floor(uint32 n) { 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n == 0) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return -1; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int log = 0; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 value = n; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 4; i >= 0; --i) { 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int shift = (1 << i); 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 x = value >> shift; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (x != 0) { 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value = x; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) log += shift; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(value, 1u); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return log; 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the integer i such as 2^(i-1) < n <= 2^i 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int Log2Ceiling(uint32 n) { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n == 0) { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return -1; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Log2Floor returns -1 for 0, so the following works correctly for n=1. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1 + Log2Floor(n - 1); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace bits 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // BASE_BITS_H_ 48