Bit twiddling in C: how to convert from 2^N to N?

Question

What is a good bit-twiddling routine to convert a number in the range [2^N,2^(N-1)-1] to N?

Some examples:

f(1) -> 0
f([2-3]) -> 1
f([4-7]) -> 2
f([8-15]) -> 3

Here is one implementation:

uint f(uint num)
{
    for (uint shifts = 0; num; shifts++) 
        num >>= 1;
    return (shifts - 1);
}

possible duplicate of [How to get lg2 of a number that is 2^k](http://stackoverflow.com/questions/2213825/how-to-get-lg2-of-a-number-that-is-2k) — kennytm, Nov 13 '10 at 18:27

score 4 · Accepted Answer · answered Nov 13 '10 at 18:23

Depending on how wide your data-type is, and how much memory you have available, a lookup-table is one possibility. It's almost certainly the fastest approach.

For other approaches, see http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious, and the subsequent sections.

score 3 · Answer 2 · answered Nov 13 '10 at 19:59

3

As most general approach, binary search may help. For values 0..31 it need only 5 stages.

y = 0;
if(x >= 0x10000<<y) y += 0x10;
if(x >= 0x100<<y) y += 0x08;
if(x >= 0x10<<y) y += 0x04;
if(x >= 0x4<<y) y += 0x02;
if(x >= 0x2<<y) y += 0x01;

answered Nov 13 '10 at 19:59

Vovanium

3,798
17
23

ruslik · Answer 3 · 2010-11-13T18:36:12.090

1

Take a look at hacks for computing base 2 logarithm (or leading zero count, they are the same) on this page: http://www-graphics.stanford.edu/~seander/bithacks.html

You could also find useful the function __builtin_clz (or _BitScanReverse for VS) for x86.

edited Nov 13 '10 at 18:36

answered Nov 13 '10 at 18:28

ruslik

14,714
1
39
40

Bit twiddling in C: how to convert from 2^N to N?

3 Answers3