如何在C++中执行整数log2()？

Question

在C++标准库中,我发现只有一个浮点日志方法.现在我使用log来查找二叉树中的索引级别(floor(2log(index))).

代码(C++):

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

我担心对于某些边元素(值为2 ^ n的元素),log将返回n-1.999999999999而不是n.0.这种恐惧是否正确？如何修改我的陈述以便始终返回正确的答案？

Answer 1

如果您使用的是最新版本的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 2

您可以使用此方法:

int targetlevel = 0;
while (index >>= 1) ++targetlevel;

注意:这将修改索引.如果您不需要它,请创建另一个临时int.

极端情况是当index为0.你可能应该单独检查它并抛出异常或返回错误,如果index == 0.

Answer 3

如果您只想要一个快速整数log ₂操作,以下函数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的补数中设置的最高位).我不建议使用它们,除非速度至关重要(我更喜欢可读性)但你应该意识到它们存在.

Answer 4

Base-2整数对数

这是我为64位无符号整数所做的.这计算base-2对数的下限,相当于最高位的索引.这种方法对于大数字来说非常快,因为它使用的是一个展开的循环,它始终以log264 = 6步执行.

从本质上讲,它所做的是逐渐减去序列{0≤k≤5:2 ^(2 ^ k)} = {2³²,2¹⁶,2⁸,2⁴,2²,2¹} = {4294967296,65536,256 ,16,4,2,1}并且对减去的值的指数k求和.

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

请注意,如果给出无效输入0(这是初始-(n == 0)检查的内容),则返回-1 .如果您从未期望调用它n == 0,则可以替换int i = 0;初始化程序并assert(n != 0);在函数入口处添加.

基数为10的整数对数

基数为10的整数对数可以使用类似的方法计算 - 最大的平方测试为10 15,因为log 102⁶⁴⁶⁴19.2659......

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

Answer 5

从C++20开始，您可以使用

std::bit_width(index) - 1

非常简短、紧凑、快速且可读。

它遵循与Igor Krivokon 提供的答案相同的想法。

Answer 6

这已在上述评论中提出.使用gcc builtins:

static inline int log2i(int x) {
    assert(x > 0);

    return sizeof(int) * 8 - __builtin_clz(x) - 1;
}

static void test_log2i(void) {
    assert_se(log2i(1) == 0);
    assert_se(log2i(2) == 1);
    assert_se(log2i(3) == 1);
    assert_se(log2i(4) == 2);
    assert_se(log2i(32) == 5);
    assert_se(log2i(33) == 5);
    assert_se(log2i(63) == 5);
    assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}

Answer 7

如果您使用的是 C++11，您可以将其设为 constexpr 函数：

constexpr std::uint32_t log2(std::uint32_t n) noexcept
{
    return (n > 1) ? 1 + log2(n >> 1) : 0;
}