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?
Already answered by abamert but just to be more concrete this is how you would code it:
Log2(x) = result
while (x >>= 1) result++;
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With