How to compute log base 2 using bitwise operators?

Question

I need to compute the log base 2 of a number in C but I cannot use the math library. The answer doesn't need to be exact, just to the closest int. I've thought about it and I know I could just use a while loop and keep dividing the number by 2 until it is < 2, and keep count of the iterations, but is this possible using bitwise operators?

Answer 1

If you count shifting as a bitwise operator, this is easy.

You already know how to do it by successive division by 2.

x >> 1 is the same as x / 2 for any unsigned integer in C.

If you need to make this faster, you can do a "divide and conquer"—shift, say, 4 bits at a time until you reach 0, then go back and look at the last 4 bits. That means at most 16 shifts and 19 compares instead of 63 of each. Whether it's actually faster on a modern CPU, I couldn't say without testing. And you can take this a step farther, to first do groups of 16, then 4, then 1. Probably not useful here, but if you had some 1024-bit integers, it might be worth considering.

Answer 2

Already answered by abamert but just to be more concrete this is how you would code it:

Log2(x) = result
while (x >>= 1) result++;