CODEWITHSUNDEEP
cbit-manipulationlogarithmbinary-log
SKLAK
SKLAK

Reputation: 3965

How to compute log base 2 using bitwise operators?

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?

Upvotes: 17

Views: 38339

Answers (4)

Nathan Myers
Nathan Myers

Reputation: 71

If you can compile with an up-to-date C++ compiler instead, you can use

  #include <bit>
  int log2(auto i) { return 8*sizeof(i) - std::countl_zero(i) - 1; }

portably.

With g++ or clang, that would be using "-std=c++20", or later. This will use the "bsr" instruction on x86, much faster than a loop.

Upvotes: 4

user19746357
user19746357

Reputation: 71

__builtin_clz(x): This function is used to count the leading zeros of the integer. Note : clz = count leading zero’s (In C/ C++). Considering 32 bit Integer,

log_2_x = 32 - __builtin_clz(x) - 1;

Upvotes: 7

Caesar De la Paz III
Caesar De la Paz III

Reputation: 387

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

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

Upvotes: 21

abarnert
abarnert

Reputation: 365787

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.

Upvotes: 18

Related Questions