如何在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) {

  uint32_t y;

  asm ( "\tbsr %1, %0\n"

      : "=r"(y)

      : "r" (x)

  );

  return y;

}

Answer 3

如果只想进行快速整数log 2操作，则可以使用以下函数mylog2()，而不必担心浮点精度：

#include <limits.h>

static unsigned int mylog2 (unsigned int val) {

    if (val == 0) return UINT_MAX;

    if (val == 1) return 0;

    unsigned int ret = 0;

    while (val > 1) {

        val >>= 1;

        ret++;

    }

    return ret;

}

#include <stdio.h>

int main (void) {

    for (unsigned int i = 0; i < 20; i++)

        printf ("%u -> %u\n", i, mylog2(i));

    putchar ('\n');

    for (unsigned int i = 0; i < 10; i++)

        printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));

    return 0;

}

上面的代码还具有一个小的测试工具，因此您可以检查行为：

0 -> 4294967295

1 -> 0

2 -> 1

3 -> 1

4 -> 2

5 -> 2

6 -> 2

7 -> 2

8 -> 3

9 -> 3

10 -> 3

11 -> 3

12 -> 3

13 -> 3

14 -> 3

15 -> 3

16 -> 4

17 -> 4

18 -> 4

19 -> 4

4294967286 -> 31

4294967287 -> 31

4294967288 -> 31

4294967289 -> 31

4294967290 -> 31

4294967291 -> 31

4294967292 -> 31

4294967293 -> 31

4294967294 -> 31

4294967295 -> 31

它将返回UINT_MAX输入值0来指示未定义的结果，因此您应检查一下（没有有效的无符号整数的对数应很高）。

顺便说一句，有一些疯狂的快速黑客做的正是这一点（找到最高位2的补数设置），可从这里。除非速度至关重要（我个人更喜欢可读性），否则我不建议使用它们，但是应该使您意识到它们的存在。