CODEWITHSUNDEEP
c++performancebinarybig-obit
user2015064
user2015064

Reputation:

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.

Upvotes: 2

Views: 1648

Answers (2)

TuanDT
TuanDT

Reputation: 1667

Here's my one liner answer, but it depends on how log2() is implemented in your machine.

length = ceil(log2(number))

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

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];
}

Upvotes: 6

Related Questions