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

Question

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

所以100给出" 1100100 "(长度为7)

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

Answer 1

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

一种简单的方法使用查找表.首先,在启动时制作一个查找表:

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