类似地，值向下舍入到 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 并转换为整数更好，对吗？
最佳答案
是的，
- 四舍五入到下一个较低的 2 次方并取对数相当于取取底对数，并且
- 四舍五入到下一个更大的 2 的幂并取对数相当于取上限对数。
仅当我们忽略 log2(0.1) 的边缘情况时，这些等价才成立，其中 floor(log2(0.1)) 与 不同log2(0).
请注意，您可以使用 std::bit_width(x) - 1 获取任何整数 x 的底二进制对数。上限对数也可以通过这种方式获得；如果 x 不是 2 的幂，则只需递增即可。
But it still has to be better than calling
logand converting to integer, right?
并不明显它会变慢。浮点运算可能有硬件支持，并且原则上可以更快。尤其是 sqrt 速度快得惊人。我不知道有任何架构具有快速内置对数指令。 x87指令相对较慢。
如有疑问，您应该进行分析。
另请参阅
关于c++ - 查找以 2 为底的对数向上舍入为整数，与向上舍入到 2 的幂并查找最高设置位相同吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/77243973/