如何计算 O(1) 中的二进制长度？

Question

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

所以100给出“1100100”（长度为7）

但它是一个 O(n) 算法（至少），我正在编写一个需要大量位计数的性能密集型程序。有没有什么算法可以让我们知道任何给定 'binary' 数字的长度，而不必立即将数字预先转换为 std::string？谢谢。

Answer 1

中描述了多种方法

一种简单的方法是使用查找 table。首先，在启动时查找table：

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

现在可以按如下方式使用：

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

Answer 2

这是我的一个线性答案，但这取决于 log2() 在您的机器中是如何实现的。

length = ceil(log2(number))

如何计算 O(1) 中的二进制长度？

How to count binary length in O(1)?

c++

binary

performance

big-o

bit