14

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?

hippietrail
  • 15,848
  • 18
  • 99
  • 158
SKLAK
  • 3,825
  • 9
  • 33
  • 57
  • 3
    Do you count [shifting](http://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) as a bitwise operator? If so, the answer is pretty obvious. If not, it's trickier. – abarnert Feb 08 '13 at 06:59
  • 0_o Why can't you use the math library? –  Feb 08 '13 at 06:59
  • 2
    @JackManey: Presumably this is either homework, or the self-teaching equivalent. But that's fine; he seems to have put some effort into it (he always has a working solution), and is looking for hints to see if there's another way to do it, not asking us to do his homework for him. – abarnert Feb 08 '13 at 07:02
  • 2
    @JackManey: The math library only computes logarithms for floating point numbers, if you have a 64-bit number slightly below a power of two but larger than 2^56 then `log2()` *will* give you a wrong answer. – Dietrich Epp Feb 08 '13 at 07:04
  • Also see [my answer to Determine which single bit in the byte is set](http://stackoverflow.com/questions/14429661/determine-which-single-bit-in-the-byte-is-set/14429782#14429782) – John Dvorak Feb 08 '13 at 07:06
  • 1
    you can go through [Find the log base 2 of an N-bit integer in O(lg(N)) operations](http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog) in below link - http://graphics.stanford.edu/~seander/bithacks.html – rajneesh Feb 08 '13 at 07:03
  • Can you quote the relevant ones here? Link-only answers are not welcome here, and your link is not even clickable. – John Dvorak Feb 08 '13 at 07:04
  • That's true, but it doesn't have any ways to answer this problem with nothing but bitwise operations, unless you count shifting, in which case it has only the obvious one. It does have some really clever tricks using a combination of bitwise and arithmetic and/or table-lookup operations. (Whether they'd actually be faster on a modern CPU, I'm not sure; if it ever mattered, I'd have to test…) – abarnert Feb 08 '13 at 07:06
  • Also, I think anyone asking this question (or searching for it later) will be interested in a lot of the stuff in that document, so, even if this doesn't directly answer the question, I'm not sure why it's getting downvoted. – abarnert Feb 08 '13 at 07:08
  • @abarnert links are good. Links-only are bad. Quoting from external (but not "stealing") resources is good. – John Dvorak Feb 08 '13 at 07:10
  • answer is pointing to relevant section in the link. they provide mutiple solution to problem its pointless to copy past from link to answer. – rajneesh Feb 08 '13 at 07:13

4 Answers4

19

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

Log2(x) = result
while (x >>= 1) result++;
sashkello
  • 17,306
  • 24
  • 81
  • 109
Caesar De la Paz III
  • 347
  • 3
  • 8
16

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.

abarnert
  • 354,177
  • 51
  • 601
  • 671
  • Thanks, I didn't realize how obvious it was. I figured it out. – SKLAK Feb 08 '13 at 07:11
  • @SKLAK: For extra fun, try compiling the `/2` and `>>1` code with -O2 and see how it differs. If one is significantly faster than the other, you may well get the exact same code for both. – abarnert Feb 08 '13 at 07:14
  • They'll only be the same for `unsigned`. For `int`, there's an extra operation to add the sign bit beforehand, which ensures that the result rounds towards zero rather than negative infinity. – Dietrich Epp Feb 08 '13 at 07:19
  • @DietrichEpp: That's already in the answer, so I didn't think it needed to be mentioned again in the comment. – abarnert Feb 08 '13 at 07:37
  • @SKLAK: From a quick test, on an x86_64 with Apple clang 4.1 -O2, doing one step of divide-and-conquer gives a 2.9x speedup on 64-bit numbers, and two steps a 3.3x, but the fastest method from rajneesh's link is 5.8x faster (assuming I modified those algorithms for 64-bitness correctly). It's not nearly as dramatic for 32-bit numbers. Anyway, if you don't need the speed, I'd go with the simple version for readability—but it's worth reading those other algorithms for enlightenment. – abarnert Feb 08 '13 at 07:41
3

__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;
user19746357
  • 31
  • 1
  • What you are recommending is good. But `__builtin_clz()` is a compiler specific function. It's only available on GCC. – HufF867 Jan 16 '23 at 05:34
1

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.

Nathan Myers
  • 41
  • 2