How to do an integer log2() in C++?

Question

In the C++ standard libraries I found only a floating point log method. Now I use log to find the level of an index in a binary tree ( floor(2log(index)) ).

Code (C++):

int targetlevel = int(log(index)/log(2));

I am afraid that for some of the edge elements (the elements with value 2^n) log will return n-1.999999999999 instead of n.0. Is this fear correct? How can I modify my statement so that it always will return a correct answer?

Answer 1

You can use this method instead:

int targetlevel = 0;
while (index >>= 1) ++targetlevel;

Note: this will modify index. If you need it unchanged, create another temporary int.

The corner case is when index is 0. You probably should check it separately and throw an exception or return an error if index == 0.

Answer 2

How deep do you project your tree to be? You could set a range of say... +/- 0.00000001 to the number to force it to an integer value.

I'm actually not certain you'll hit a number like 1.99999999 because your log2 should not lose any accuracy when calculating 2^n values (Since floating point rounds to the nearest power of 2).

Answer 3

int targetIndex = floor(log(i + 0.5)/log(2.0));

Answer 4

If you just want a fast integer log₂ operation, the following function will do it without having to worry about floating-point accuracy:

static unsigned int mylog2 (unsigned int val) {
    unsigned int ret = -1;
    while (val != 0) {
        val >>= 1;
        ret++;
    }
    return ret;
}

It will return -1 for an input value of 0, rather than the correct infinity (which is a little hard to represent in an integer :-)

By the way, there are some insanely fast hacks to do exactly this (find the highest bit set in a 2's complement number) available from here. I wouldn't suggest using them unless speed is of the essence (I prefer readability myself) but you should be made aware that they exist.

Answer 5

I've never had any problem with floating-point accuracy on the formula you're using (and a quick check of numbers from 1 to 2³¹ - 1 found no errors), but if you're worried, you can use this function instead, which returns the same results and is about 66% faster in my tests:

int HighestBit(int i){
    if(i == 0)
        return -1;

    int bit = 31;
    if((i & 0xFFFFFF00) == 0){
        i <<= 24;
        bit = 7;
    }else if((i & 0xFFFF0000) == 0){
        i <<= 16;
        bit = 15;
    }else if((i & 0xFF000000) == 0){
        i <<= 8;
        bit = 23;
    }

    if((i & 0xF0000000) == 0){
        i <<= 4;
        bit -= 4;
    }

    while((i & 0x80000000) == 0){
        i <<= 1;
        bit--;
    }

    return bit; 
}

Answer 6

If you are on a recent-ish x86 or x86-64 platform (and you probably are), use the bsr instruction which will return the position of the highest set bit in an unsigned integer. It turns out that this is exactly the same as log2(). Here is a short C or C++ function that invokes bsr using inline ASM:

#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

Answer 7

This isn't standard or necessarily portable, but it will in general work. I don't know how efficient it is.

Convert the integer index into a floating-point number of sufficient precision. The representation will be exact, assuming the precision is sufficient.

Look up the representation of IEEE floating-point numbers, extract the exponent, and make the necessary adjustment to find the base 2 log.