求以 2 为底的对数向上舍入为整数，与向上舍入到 2 的幂并找到最高设置位相同吗？

Question

类似地，将值向下舍入到 2 的幂并找到最右边的设置位相当于以 2 为底的对数向下舍入到整数。这是正确的吗？

我认为这会起作用，对于任何数字四舍五入到 2 的幂，并执行 C++ 中的 countr_zero() 或 MSVC 中的 bitscan 函数或 GCC 中的 __builtin_ctz()。这行得通吗？这肯定比 log 函数要好得多，log 函数（根据我的理解）可能是 CPU 可以执行的最慢的计算。

有趣的是，这样做本身涉及相当多的步骤：

//Round up to power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

虽然 count_zero 看起来像：

usize countr_zero(u64 x) {
  if (x == 0)
    return 64;
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  constexpr std::array<usize, 64> table = {
      0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
      5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
      63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
      62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58};
  return table[(x & ~x + 1) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}

但是它仍然比调用 log 并转换为整数更好，对吧？

Answer 1

是的，

• 四舍五入到下一个较低的 2 次方并取对数相当于取取底对数，并且
• 四舍五入到下一个更大的 2 的幂并取对数相当于取上限对数。

仅当我们忽略

log2(0.1)

的边缘情况时，这些等价才成立，其中

floor(log2(0.1))

与

log2(0)

不同。

请注意，您可以使用

x

获得任何整数

std::bit_width(x) - 1

的取底二进制对数。上限对数也可以通过这种方式获得；如果

x

不是 2 的幂，则只需递增即可。

但它仍然比调用

log

并转换为整数更好，对吧？

并不明显会变慢。浮点运算可能有硬件支持，并且原则上可以更快。尤其是

sqrt

速度快得惊人。我不知道有任何架构具有快速内置对数指令。 x87指令相对较慢。

如有疑问，您应该进行分析。

另请参阅

• 如何快速计算任意底数的整数对数？
• 肖恩·埃伦·安德森 (Sean Eron Anderson) 的 Bit Twiddling Hacks