log2 of an integer that is a power of 2

Is there an efficient way to find the log2 of a number assuming it's a power of 2. I know the obvious ways like having a table or

for (log2=0;x!=1;x>>=1,log2++);

But I am wondering if there is a more efficient/elegant way.

Solution

You can just count the number of leading or trailing zero bits, because any exact power-of-two is represented as a single 1 bit, with all other bits 0. Many CPUs have special instructions for doing this, and compilers such as gcc have intrinsics for these operations, which get compiled to a single instruction on appropriate architectures.

If you have an efficient clz ("count leading zeroes") then a log2 implementation might look like this:

int32_t ilog2(uint32_t x)
{
    return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1;
}

(Note: returns -1 for ilog2(0).)

When using gcc or a gcc-compatible compiler you can just define clz like this:

#define clz(x) __builtin_clz(x)

Microsoft has something similar: BitScanReverse.

Note that it might appear more convenient to count trailing zeroes (using a ctz instruction), but a clz instruction is more widely available on different CPU architectures.

A further bonus of using clz rather than ctz is that you get floor(log2(x)) for non-power-of-2 values, making your ilog2 function more generally useful than if you had used ctz, which only works for exact powers-of-2.