如何使用按位运算符计算以 2 为底的对数？

Question

我需要用 C 语言计算一个数字的以 2 为底的对数，但我不能使用数学库。答案不需要很精确，只要最接近的整数即可。我已经考虑过了，我知道我可以只使用一个 while 循环并继续将数字除以 2，直到它是 < 2, and keep count of the iterations, but is this possible using bitwise operators?

Answer 1

已由 abamert 回答，但更具体地说，这就是您的编码方式：

Log2(x) = result
while (x >>= 1) result++;   

Answer 2

如果将shifting算作按位运算符，这很容易。

你已经知道如何通过连续除以 2 来做到这一点。

x >> 1

与 C 中任何无符号整数的

x / 2

相同。

如果你需要让它更快，你可以做一个“分而治之”——比如说，一次移动 4 位直到你达到 0，然后返回并查看最后 4 位。这意味着最多 16 次轮班和 19 次比较，而不是每次 63 次。它在现代 CPU 上是否真的更快，未经测试我不能说。你可以更进一步，先做 16 组，然后 4 组，然后 1 组。在这里可能没有用，但如果你有一些 1024 位整数，可能值得考虑。

Answer 3

__builtin_clz(x)：此函数用于计算整数的前导零。注意：clz = 计数前导零（在 C/C++ 中）。 考虑到 32 位整数，

log_2_x = 32 - __builtin_clz(x) - 1;

Answer 4

如果您可以使用最新的 C++ 编译器进行编译，则可以使用

  #include <bit>
  int log2(auto i) { return 8*sizeof(i) - std::countl_zero(i) - 1; }

便携。

对于 g++ 或 clang，将使用“-std=c++20”或更高版本。这将在 x86 上使用“bsr”指令，比循环快得多。