如何使用按位运算符计算日志库2？

我需要计算在C中的数字的日志基数2，但我不能使用数学库。答案不需要是精确的，只需要最接近的int。我已经考虑过了，我知道我可以使用while循环，并将数字除以2直到它为< 2，并且保持迭代次数，但是这可能使用按位运算符吗？如何使用按位运算符计算日志库2？

来源

2013-02-08 SKLAK

你算[移位]（http://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts ）作为一个按位运算符？如果是这样，答案是非常明显的。如果不是，那就更棘手了。 – abarnert

0_o为什么你不能使用数学库？ – 2013-02-08 06:59:56

@JackManey：据推测这可能是家庭作业，也可能是自学教学。但没关系;他似乎已经付出了一些努力（他总是有一个工作解决方案），并且正在寻找暗示，看看是否有另一种方式去做，而不是要求我们为他做功课。 – abarnert

如果你把shifting算作一个按位运算符，这很容易。

你已经知道了如何通过连续除以2

x >> 1做到这一点是一样的x/2在C.

任何无符号整数，如果你需要，使这个速度，你可以做一个“分而治之” - 一次转换4位，直到你达到0，然后返回查看最后4位。这意味着最多16班和19比较，而不是每个63。无论现代CPU的速度如何，我都说不经过测试。你可以更进一步，先做16组，然后是4组，然后是1.这里可能没有用，但如果你有一些1024位整数，可能值得考虑。

来源

2013-02-08 07:03:18 abarnert

谢谢，我不知道它有多明显。我想到了。 – SKLAK

@SKLAK：为了获得更多乐趣，请尝试使用-O2编译'/ 2'和'>> 1'并查看它的不同之处。如果一个比另一个快得多，那么你可能会得到完全相同的代码。 – abarnert

它们只会与'unsigned'相同。对于'int'，还有一个额外的操作来预先添加符号位，这可以确保结果朝向零而不是负无穷大。 –

已经通过abamert回答，但只是为了更具体，这是你将如何编写它：

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

来源

2013-08-09 04:21:23

如何使用按位运算符计算日志库2？

回答

相关问题