<分区>
假设它是 2 的幂，是否有一种有效的方法来查找数字的 log2。我知道很明显的方法，比如有一个表或
for (log2=0;x!=1;x>>=1,log2++);
但我想知道是否有更高效/优雅的方式。
<分区>
假设它是 2 的幂，是否有一种有效的方法来查找数字的 log2。我知道很明显的方法，比如有一个表或
for (log2=0;x!=1;x>>=1,log2++);
但我想知道是否有更高效/优雅的方式。
最佳答案
您可以只计算前导或尾随零位的数量，因为任何精确的 2 的幂都表示为单个 1 位，所有其他位都为 0。许多 CPU 有专门的指令来执行此操作，编译器如因为 gcc 具有这些操作的内在函数，这些操作在适当的体系结构上被编译为单个指令。
如果您有一个高效的 clz(“计算前导零”)，那么 log2 实现可能如下所示:
int32_t ilog2(uint32_t x)
{
return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1;
}
(注意:对于 ilog2(0) 返回 -1。)
当使用 gcc 或兼容 gcc 的编译器时，您可以像这样定义 clz:
#define clz(x) __builtin_clz(x)
Microsoft 有类似的东西:BitScanReverse .
请注意，计算尾随 零似乎更方便(使用ctz 指令)，但是a clz instruction is more widely available on different CPU architectures .
使用 clz 而不是 ctz 的另一个好处是你得到 floor(log2(x)) 非幂-2 值，使您的 ilog2 函数比您使用 ctz 时更有用，后者仅适用于精确的 2 的幂。
关于c++ - 2 的幂的整数的 log2，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47074126/