如何计算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.

通常,我必须在std :: string中将整数转换为二进制,然后使用方法std :: string :: size()来获取二进制数的长度。

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

所以100给出“1100100”(长度为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.

但它是一个O(n)算法(至少),我正在编写一个性能密集型程序,需要大量的位计数。是否有任何算法可以让我们知道任何给定的'二进制'数字的长度,而无需事先将数字转换为std :: string?谢谢。

2 个解决方案

#1

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

您正在计算二进制对数。有很多方法可以做到这一点,在bit twiddling hacks页面上有所描述。

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

#2

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

这是我的单线答案,但这取决于你的机器中如何实现log2()。

length = ceil(log2(number))

#1