log2 of an integer that is a power of 2 [duplicate]

Question

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.

Answer 1

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.

See also: Finding the first set bit in a binary number.

Answer 2

I haven't benchmarked this, but it ought to run reasonably fast since it doesn't require many iterations:

int which_power_of_2(uint64_t x) {
    uint64_t z = 0x0000000100000000ULL;
    int p = 31, d = 16;
    while (d) {
        if (x & (z-1)) {
            p -= d;
            z >>= d;
        }
        else {
            p += d;
            z <<= d;
        }
        d >>= 1;
    }
    return x ? ((x & z) ? p+1 : p) : -1;
}