CODEWITHSUNDEEP
c++bit-manipulationbit
Matt Wamboldt
Matt Wamboldt

Reputation: 581

What is the fastest way to calculate the number of bits needed to store a number

I'm trying to optimize some bit packing and unpacking routines. In order to do the packing I need to calculate the number of bits needed to store integer values. Here is the current code.

if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
    ++r;
    n >>= 1;
}
return r;

Upvotes: 9

Views: 9498

Answers (6)

Yevhen
Yevhen

Reputation: 1965

number_of_bits = log2(integer_number)

rounded to the higher integer.

Upvotes: 2

Michael Burr
Michael Burr

Reputation: 340316

You're looking to determine the integer log base 2 of a number (the l=highest bit set). Sean Anderson's "Bit Twiddling Hacks" page has several methods ranging from the obvious counting bits in a loop to versions that use table lookup. Note that most of the methods demonstrated will need to be modified a bit to work with 64-bit ints if that kind of portability is important to you.

Just make sure that any shifting you're using to work out the highest bit set needs to be done' on an unsigned version of the number since a compiler implementation might or might not sign extend the >> operation on a signed value.

Upvotes: 6

Ron
Ron

Reputation: 269

You would have to check the execution time to figure the granularity, but my guess is that doing 4 bits at a time, and then reverting to one bit at a time would make it faster. Log operations would probably be slower than logical/bit operations.

if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
  r+=4;
  n >>= 4; }
while (n) {
  r++;
  n >>= 1; }
return r;

Upvotes: 3

dan04
dan04

Reputation: 91179

Do a binary search instead of a linear search.

if ((n >> 16) != 0)
{
    r += 16;
    n >>= 16;
}

if ((n >> 8) != 0)
{
    r += 8;
    n >>= 8;        
}

if ((n >> 4) != 0)
{
    r += 4;
    n >>= 4;        
}

// etc.

If your hardware has bit-scan-reverse, an even faster approach would be to write your routine in assembly language. To keep your code portable, you could do

#ifdef ARCHITECTURE_WITH_BSR
   asm // ...
#else
   // Use the approach shown above
#endif

Upvotes: 3

Sparky
Sparky

Reputation: 14077

What you are trying to do is find the most significant bit. Some architectures have a special instruction just for this purpose. For those that don't, use a table lookup method.

Create a table of 256 entries, wherein each element identifies the upper most bit.

Either loop through each byte in the number, or use a few if-statements to break to find the highest order non-zero byte.

I'll let you take the rest from here.

Upvotes: 5

Marcelo Cantos
Marcelo Cantos

Reputation: 185962

Non-portably, use the bit-scan-reverse opcode available on most modern architectures. It's exposed as an intrinsic in Visual C++.

Portably, the code in the question doesn't need the edge-case handling. Why do you require one bit for storing 0? In any case, I'll ignore the edges of the problem. The guts can be done efficiently thus:

if (n >> 16) { r += 16; n >>= 16; }
if (n >>  8) { r +=  8; n >>=  8; }
if (n >>  4) { r +=  4; n >>=  4; }
if (n >>  2) { r +=  2; n >>=  2; }
if (n - 1) ++r;

Upvotes: 10

Related Questions