xersi xersi - 2 months ago 9
C++ Question

How to count binary length in O(1)?

Normally, I have to convert an integer to binary in a std::string then use the method std::string::size() to get the length of the binary number.

So 100 gives "1100100" (the length is 7)

But it is a O(n) algorithm (at least), and I am writing a performance-intensive program that requires lots of bit counting. Is there any algorithm that lets we know the length of any given 'binary' number without having to convert the number to std::string beforehand in an instant? Thanks.

Answer

You are computing a binary logarithm. There are a number of ways to do it, described on the bit twiddling hacks page.

One simple approach uses a look-up table. First, make a look-up table at start-up:

LogTable256[0] = LogTable256[1] = 0;
for (int i = 2; i != 256; i++) {
    LogTable256[i] = 1 + LogTable256[i / 2];
}
LogTable256[0] = -1; // if you want log(0) to return -1

Now you can use it as follows:

if (tt = v >> 24) {
    r = 24 + LogTable256[tt];
} else if (tt = v >> 16) {
    r = 16 + LogTable256[tt];
} else if (tt = v >> 8) {
    r = 8 + LogTable256[tt];
} else {
    r = LogTable256[v];
}