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

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

因此 100 给出了“ 1100100 ”(长度为 7 )

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

最佳答案

您正在计算二进制对数。有多种方法可以做到，如bit twiddling hacks page所述。

一种简单的方法是使用查找表。首先，在启动时创建一个查询表:

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