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

Question

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;

Answer 1

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;