如何在C ++中执行整数log2（）？

Question

在C ++标准库中，我仅找到一个浮点日志方法。现在，我使用log在二叉树（floor(2log(index))）中查找索引的级别。

代码（C ++）：

int targetlevel = int(log(index)/log(2));

恐怕对于某些边缘元素（值为2 ^ n的元素），日志将返回n-1.999999999999，而不是n.0。这种恐惧正确吗？我该如何修改我的陈述，使其始终返回正确答案？

Answer 1

您可以改用以下方法：int targetlevel = 0;while (index >>= 1) ++targetlevel;注意：这将修改索引。如果您不需要它，则创建另一个临时int。极端情况是index为0时。如果index == 0，则可能应单独检查它并引发异常或返回错误。

Answer 2

如果您使用的是最近使用的x86或x86-64平台（可能是），请使用bsr指令，该指令将以无符号整数形式返回最高设置位的位置。事实证明，这与log2（）完全相同。这是bsr使用内联ASM 调用的简短C或C ++函数：#include <stdint.h>static inline uint32_t log2(const uint32_t x) {&nbsp; uint32_t y;&nbsp; asm ( "\tbsr %1, %0\n"&nbsp; &nbsp; &nbsp; : "=r"(y)&nbsp; &nbsp; &nbsp; : "r" (x)&nbsp; );&nbsp; return y;}

Answer 3

如果只想进行快速整数log 2操作，则可以使用以下函数mylog2()，而不必担心浮点精度：#include <limits.h>static unsigned int mylog2 (unsigned int val) {&nbsp; &nbsp; if (val == 0) return UINT_MAX;&nbsp; &nbsp; if (val == 1) return 0;&nbsp; &nbsp; unsigned int ret = 0;&nbsp; &nbsp; while (val > 1) {&nbsp; &nbsp; &nbsp; &nbsp; val >>= 1;&nbsp; &nbsp; &nbsp; &nbsp; ret++;&nbsp; &nbsp; }&nbsp; &nbsp; return ret;}#include <stdio.h>int main (void) {&nbsp; &nbsp; for (unsigned int i = 0; i < 20; i++)&nbsp; &nbsp; &nbsp; &nbsp; printf ("%u -> %u\n", i, mylog2(i));&nbsp; &nbsp; putchar ('\n');&nbsp; &nbsp; for (unsigned int i = 0; i < 10; i++)&nbsp; &nbsp; &nbsp; &nbsp; printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));&nbsp; &nbsp; return 0;}上面的代码还具有一个小的测试工具，因此您可以检查行为：0 -> 42949672951 -> 02 -> 13 -> 14 -> 25 -> 26 -> 27 -> 28 -> 39 -> 310 -> 311 -> 312 -> 313 -> 314 -> 315 -> 316 -> 417 -> 418 -> 419 -> 44294967286 -> 314294967287 -> 314294967288 -> 314294967289 -> 314294967290 -> 314294967291 -> 314294967292 -> 314294967293 -> 314294967294 -> 314294967295 -> 31它将返回UINT_MAX输入值0来指示未定义的结果，因此您应检查一下（没有有效的无符号整数的对数应很高）。顺便说一句，有一些疯狂的快速黑客做的正是这一点（找到最高位2的补数设置），可从这里。除非速度至关重要（我个人更喜欢可读性），否则我不建议使用它们，但是应该使您意识到它们的存在。