How to get lg2 of a number that is 2^k

Question

What is the best solution for getting the base 2 logarithm of a number that I know is a power of two (2^k). (Of course I know only the value 2^k not k itself.)

One way I thought of doing is by subtracting 1 and then doing a bitcount:

lg2(n) = bitcount( n - 1 ) = k, iff k is an integer
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4

But is there a faster way of doing it (without caching)? Also something that doesn't involve bitcount about as fast would be nice to know?

One of the applications this is:

suppose you have bitmask
0b0110111000

and value
0b0101010101

and you are interested of
(value & bitmask) >> number of zeros in front of bitmask
(0b0101010101 & 0b0110111000) >> 3 = 0b100010

this can be done with

using bitcount
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1

or using lg2
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1 ) - 2

For it to be faster than bitcount without caching it should be faster than O(lg(k)) where k is the count of storage bits.

Coquette

Answer 1

Many architectures have a "find first one" instruction (bsr, clz, bfffo, cntlzw, etc.) which will be much faster than bit-counting approaches.

Columbine

probably the fastest way there is... ) – Coquette

Answer 2

Yes. Here's a way to do it without the bitcount in lg(n), if you know the integer in question is a power of 2.

unsigned int x = ...;
static const unsigned int arr[] = {
  // Each element in this array alternates a number of 1s equal to
  // consecutive powers of two with an equal number of 0s.
  0xAAAAAAAA, // 0b10101010..         // one 1, then one 0, ...
  0xCCCCCCCC, // 0b11001100..         // two 1s, then two 0s, ...
  0xF0F0F0F0, // 0b11110000..         // four 1s, then four 0s, ...
  0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.]
  0xFFFF0000
}

register unsigned int reg = (x & arr[0]) != 0;
reg |= ((x & arr[4]) != 0) << 4;
reg |= ((x & arr[3]) != 0) << 3;
reg |= ((x & arr[2]) != 0) << 2;
reg |= ((x & arr[1]) != 0) << 1;

// reg now has the value of lg(x).

In each of the reg |= steps, we successively test to see if any of the bits of x are shared with alternating bitmasks in arr. If they are, that means that lg(x) has bits which are in that bitmask, and we effectively add 2^k to reg, where k is the log of the length of the alternating bitmask. For example, 0xFF00FF00 is an alternating sequence of 8 ones and zeroes, so k is 3 (or lg(8)) for this bitmask.

Essentially, each reg |= ((x & arr[k]) ... step (and the initial assignment) tests whether lg(x) has bit k set. If so, we add it to reg; the sum of all those bits will be lg(x).

That looks like a lot of magic, so let's try an example. Suppose we want to know what power of 2 the value 2,048 is:

// x = 2048
//   = 1000 0000 0000

register unsigned int reg = (x & arr[0]) != 0;
// reg =       1000 0000 0000
         & ... 1010 1010 1010
       =       1000 0000 0000 != 0
// reg = 0x1 (1)        // <-- Matched! Add 2^0 to reg.

reg |= ((x & arr[4]) != 0) << 4;
// reg =     0x .. 0800
           & 0x .. 0000
       =              0 != 0
// reg = reg | (0 << 4) // <--- No match.
// reg = 0x1 | 0
// reg remains 0x1.

reg |= ((x & arr[3]) != 0) << 3;
// reg =     0x .. 0800
           & 0x .. FF00
       =            800 != 0
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg.
// reg = 0x1 | 0x8
// reg is now 0x9.         

reg |= ((x & arr[2]) != 0) << 2;
// reg =     0x .. 0800
           & 0x .. F0F0
       =              0 != 0
// reg = reg | (0 << 2) // <--- No match.
// reg = 0x9 | 0
// reg remains 0x9.        

reg |= ((x & arr[1]) != 0) << 1;
// reg =     0x .. 0800
           & 0x .. CCCC
       =            800 != 0
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg.
// reg = 0x9 | 0x2
// reg is now 0xb (11).

We see that the final value of reg is 2^0 + 2^1 + 2^3, which is indeed 11.

Whitton

This is the best approach if you don't have access to assembly instructions, but I would get rid of the array and use the constants directly. – Hebert

@x4u: This is more for illustrative/educational purposes than to show optimized code. But otherwise, I agree. – Whitton

Best non-assembly approach, though you could use the constants in-place rather than having array arr. That might save a few cycles. – Stanfill

Answer 3

If you know the number is a power of 2, you could just shift it right (>>) until it equals 0. The amount of times you shifted right (minus 1) is your k.

Edit: faster than this is the lookup table method (though you sacrifice some space, but not a ton). See http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Norvell

You have to set k = #shifted - 1; – Nahshunn

It would be slower than the bitcount method. You can do bitcount in O(lg(k)), this shifting would be in the worst case O(k). (k is count of storage bits) – Coquette

@egon - The only thing I can see that improves on lg k is the lookup table method. Answer updated. – Norvell

@Norvell - yes it feels like it... maybe someone has a great idea how to improve it. It feels it might get faster by exploiting the fact that the number is a power of 2. It has only k states to be in and it isn't a lot. – Coquette

Actually I found the solution in the article. Method 3,4 had versions if the value is a power of 2. Method 3 had a version that is faster than using bitcount. – Coquette

Answer 4

If you don't mind dealing with floats you can use log(x) / log(2).

Ize

That would be hundreds of clock cycles on most CPUs. You can do it in one cycle if you have clz or similar instruction. – Detumescence