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

您可以改用此方法：

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

注意：这将修改索引。如果需要它保持不变，请创建另一个临时 int。

极端情况是当索引为 0 时。如果索引 == 0，您可能应该单独检查它并抛出异常或返回错误。

你把你的树投射到多深？您可以将 +/- 0.00000001 的范围设置为数字，以强制其为整数值。

我实际上不确定你会达到像 1.99999999 这样的数字，因为在计算 2^n 值时，你的 log2 不应该失去任何准确性（因为浮点四舍五入到最接近的 2 的幂）。

int targetIndex = floor(log(i + 0.5)/log(2.0));

如果您只想要一个快速的整数对数₂ 操作，以下函数将执行此操作，而不必担心浮点精度：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

它将返回输入值 0 作为未定义结果的指示，因此您应该检查这一点（没有有效的无符号整数的对数会那么高）。UINT_MAX

顺便说一句，有一些非常快的技巧可以做到这一点（找到 2 补码数中设置的最高位），可以从这里获得。我不建议使用它们，除非速度至关重要（我自己更喜欢可读性），但你应该知道它们的存在。

我从未遇到过您使用的公式的浮点准确性任何问题（并且快速检查从 1 到 2³¹ - 1 的数字没有发现错误），但如果您担心，您可以改用这个函数，它返回相同的结果，并且在我的测试中快了大约 66%：

int HighestBit(int i){
    if(i == 0)
        return -1;

    int bit = 31;
    if((i & 0xFFFFFF00) == 0){
        i <<= 24;
        bit = 7;
    }else if((i & 0xFFFF0000) == 0){
        i <<= 16;
        bit = 15;
    }else if((i & 0xFF000000) == 0){
        i <<= 8;
        bit = 23;
    }

    if((i & 0xF0000000) == 0){
        i <<= 4;
        bit -= 4;
    }

    while((i & 0x80000000) == 0){
        i <<= 1;
        bit--;
    }

    return bit; 
}

如果您使用的是最新的 x86 或 x86-64 平台（您可能是），请使用该指令，该指令将返回无符号整数中最高设置位的位置。事实证明，这与 log2（） 完全相同。下面是一个使用内联 ASM 调用的简短 C 或 C++ 函数：bsrbsr

#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;
}

这不是标准的，也不一定是可移植的，但它通常可以工作。我不知道它的效率如何。

将整数索引转换为具有足够精度的浮点数。假设精度足够，表示将是准确的。

查找 IEEE 浮点数的表示形式，提取指数，并进行必要的调整以找到以 2 为底的对数。

这个函数我在这里写的

// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
  unsigned int log2Val = 0 ;
  // Count push off bits to right until 0
  // 101 => 10 => 1 => 0
  // which means hibit was 3rd bit, its value is 2^3
  while( x>>=1 ) log2Val++;  // div by 2 until find log2.  log_2(63)=5.97, so
  // take that as 5, (this is a traditional integer function!)
  // eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
  return log2Val ;
}

此函数确定表示数值间隔所需的位数：[0..maxvalue]。

unsigned binary_depth( unsigned maxvalue )
   {
   int depth=0;
   while ( maxvalue ) maxvalue>>=1, depth++;
   return depth;
   }

通过从结果中减去 1，你得到 ，这是 2 的幂的精确表示。floor(log2(x))log2(x)x

xyy-1
00-1
110
221
321
432
532
632
732
843

这在上面的评论中已经提出。使用 gcc 内置函数：

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);
}

以 2 为底的整数对数

这是我对 64 位无符号整数所做的操作。这将计算以 2 为底的对数的下限，该底数相当于最高有效位的索引。这种方法对于大数字来说非常快，因为它使用一个展开的循环，该循环始终以 log₂64 = 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（这是初始值检查的内容），这将返回 –1。如果您从未期望使用 调用它，则可以替换初始值设定项并在函数的入口处添加。-(n == 0)n == 0int i = 0;assert(n != 0);

以 10 为底的整数对数

以 10 为底的整数对数可以使用类似的方式计算——要测试的最大平方是 10¹⁶，因为 log₁₀2⁶⁴ ≅ 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
}

请注意，一个好的编译器会将此处的整数除法运算优化为乘法指令，因为除法总是由一个常数来计算。（这很重要，因为与乘法指令相比，即使在最快的现代 CPU 上，整数除法指令仍然非常慢。

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

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

上面也有类似的答案。这个答案

1. 适用于 64 位数字
2. 允许您选择舍入类型和
3. 包括测试/示例代码

功能：

    static int floorLog2(int64_t x)
    { 
      assert(x > 0);
      return 63 - __builtin_clzl(x);
    }

    static int ceilLog2(int64_t x)
    {
      if (x == 1)
        // On my system __builtin_clzl(0) returns 63.  64 would make more sense   
        // and would be more consistent.  According to stackoverflow this result  
        // can get even stranger and you should just avoid __builtin_clzl(0).     
        return 0;
      else
        return floorLog2(x-1) + 1;
    }

测试代码：

for (int i = 1; i < 35; i++)
  std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
           <<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;

重写托德·雷曼（Todd Lehman）的答案，使其更通用：

#include <climits>

template<typename N>
constexpr N ilog2(N n) {
    N i = 0;
    for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
        if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
    }
    return i;
}

Clang with 展开循环：-O3

0000000100000f50    pushq   %rbp
0000000100000f51    movq    %rsp, %rbp
0000000100000f54    xorl    %eax, %eax
0000000100000f56    cmpl    $0xffff, %edi
0000000100000f5c    setg    %al
0000000100000f5f    shll    $0x4, %eax
0000000100000f62    movl    %eax, %ecx
0000000100000f64    sarl    %cl, %edi
0000000100000f66    xorl    %edx, %edx
0000000100000f68    cmpl    $0xff, %edi
0000000100000f6e    setg    %dl
0000000100000f71    leal    (,%rdx,8), %ecx
0000000100000f78    sarl    %cl, %edi
0000000100000f7a    leal    (%rax,%rdx,8), %eax
0000000100000f7d    xorl    %edx, %edx
0000000100000f7f    cmpl    $0xf, %edi
0000000100000f82    setg    %dl
0000000100000f85    leal    (,%rdx,4), %ecx
0000000100000f8c    sarl    %cl, %edi
0000000100000f8e    leal    (%rax,%rdx,4), %eax
0000000100000f91    xorl    %edx, %edx
0000000100000f93    cmpl    $0x3, %edi
0000000100000f96    setg    %dl
0000000100000f99    leal    (%rdx,%rdx), %ecx
0000000100000f9c    sarl    %cl, %edi
0000000100000f9e    leal    (%rax,%rdx,2), %ecx
0000000100000fa1    xorl    %eax, %eax
0000000100000fa3    cmpl    $0x1, %edi
0000000100000fa6    setg    %al
0000000100000fa9    orl %ecx, %eax
0000000100000fab    popq    %rbp

当为常量时，在编译时计算结果。n

给定浮点数的工作方式（粗略地说，尾数 * 2^ 指数），那么任何不超过 2^127 的 2 次幂的数字都将被准确表示，而不会出错。

这确实给出了一个简单但相当棘手的解决方案 - 将浮点数的位模式解释为整数，然后只看指数。这是上面 David Thornley 的解决方案。

float f = 1;
for (int i = 0; i < 128; i++)
{
    int x = (*(int*)(&f)>>23) - 127;
    int l = int(log(f) / log(2));

    printf("i = %d, log = %d, f = %f quick = %d\n",
        i, l, f, x);
    f *= 2;
}

任何整数都可以表示为浮点数是不正确的 - 只有那些位数少于尾数才能表示的整数。在 32 位浮点数中，这是 23 位的值。

使用 GCC：

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

假设你的 X 是 > 0

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

std::bit_width(index) - 1

非常短小精悍，快速且可读性强。

它遵循与伊戈尔·克里沃孔（Igor Krivokon）提供的答案相同的想法。