CODEWITHSUNDEEP
cbit-manipulation
asdf.ghjk
asdf.ghjk

Reputation: 23

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

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

Some examples:

Here is one implementation:

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

Upvotes: 2

Views: 292

Answers (3)

Vovanium
Vovanium

Reputation: 3888

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;

Upvotes: 3

ruslik
ruslik

Reputation: 14880

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.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272517

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.

Upvotes: 4

Related Questions