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

Question

我需要在C语言中计算一个数字的以2为底的对数，但我不能使用math库。答案不需要精确到小数，只需最接近整数即可。我已经思考过了，我知道可以使用while循环，反复除以2直到数值小于2，并记录迭代次数，但是是否可能使用位运算符？

- SKLAK

---

你认为“位移操作”也算作是一种位运算符吗？如果是，答案显而易见。如果不是，那就比较棘手了。 - abarnert

@JackManey：很可能这是作业，或者是自学的等价物。但没关系；他似乎已经付出了一些努力（他总是有一个可行的解决方案），并且正在寻找提示以查看是否有其他方法来完成它，而不是要求我们替他完成作业。 - abarnert

你可以通过下面的链接查看在O(lg(N))的操作中，找到一个N位整数的以2为底的对数：Find the log base 2 of an N-bit integer in O(lg(N)) operations - http://graphics.stanford.edu/~seander/bithacks.html - rajneesh

@JackManey：数学库仅计算浮点数的对数，如果您有一个略小于2的幂但大于2^56的64位数字，则log2()将会给出错误的答案。 - Dietrich Epp

还可以查看我的回答，确定字节中设置了哪个单个位。 - John Dvorak

Answer 1

虽然已经有abamert回答了，但为了更加明确，下面是如何编写代码：

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

- Caesar De la Paz III

---

杰出的答案 - John Nyingi

Answer 2

如果您将shifting视为位运算符，那么这很容易。
您已经知道如何通过连续除以2来实现。
x >> 1 对于C语言中的任何无符号整数而言，等同于x / 2。
如果您需要使此过程更快，可以使用“分而治之”的方法 - 每次移动4位，直到达到0，然后返回并查看最后4位。这意味着最多要进行16次移位和19次比较，而不是每个63次。在现代CPU上是否真正更快，我无法在测试之前说。您还可以进一步采取以下措施，首先对16个整数进行分组，然后对4个整数进行分组，最后对1个整数进行分组。也许在这里没有用，但如果您有一些1024位的整数，这可能值得考虑。

- abarnert

---

谢谢，我没有意识到它是多么显而易见。我已经想通了。 - SKLAK

@SKLAK：为了增加乐趣，尝试使用-O2编译/2和>>1代码，并查看它们之间的区别。如果其中一个明显比另一个快，你可能会得到两者完全相同的代码。 - abarnert

只有对于“unsigned”它们才是相同的。对于“int”，需要在执行操作之前添加符号位，以确保结果向零舍入而不是负无穷大。 - Dietrich Epp

@DietrichEpp：这已经在答案中了，所以我认为在评论中不需要再提到它。 - abarnert

@SKLAK：从快速测试来看，在使用苹果clang 4.1 -O2的x86_64上，对64位数字进行一步分治可以提高2.9倍的速度，两步则为3.3倍，但是从rajneesh的链接中最快的方法要快5.8倍（假设我正确地修改了这些算法以适应64位）。对于32位数字来说，效果并不明显。无论如何，如果您不需要速度，我建议选择简单版本以提高可读性，但值得阅读其他算法以获得启示。 - abarnert

Answer 3

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

log_2_x = 32 - __builtin_clz(x) - 1;

- user19746357

---

你所推荐的很好。但是__builtin_clz()是一个编译器特定的函数，只能在GCC上使用。 - HufF867

你推荐的方法很好。但是__builtin_clz()是一个特定于编译器的函数，只在GCC上可用。 - undefined

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”指令，比循环要快得多。

- Nathan Myers