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

StackOverflow https://stackoverflow.com/questions/994593

题

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

代码（C++）：

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

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

有帮助吗？

解决方案

可以使用此方法来代替：

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

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

在转角的情况是当索引为0你或许应该分别检查它并抛出异常，或者返回一个错误，如果索引== 0。

其他提示

如果您是在最近十岁上下的x86或x86-64的平台（你可能是），使用bsr指令，将返回一个无符号整数最高设置位的位置。事实证明，这是完全一样的log 2（）。下面是使用内联ASM调用bsr短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;
}

如果你只是想要一个快速整数日志 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的补数设置），可从的此处。我不建议使用它们，除非速度是精华（我更喜欢自己的可读性），但你应该知道它们的存在。

基-2-整数对数

下面是我对64位无符号整数做。此计算基本-2对数，这相当于最显著位的索引的楼层。这种方法是 smokingly快为大量，因为它使用的展开循环，在log₂64= 6个步骤总是执行。

本质上，它的作用是减去远逐渐变小的正方形的序列中的{0≤ķ≤5：2 ^（2 ^ k）的} = {2³²，2 16，2⁸，2⁴，2 2，2 1} = {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
}

请注意，此返回-1如果给予0无效的输入（这是初始-(n == 0)是用于检查）。如果你休想用n == 0调用它，你可以为初始化替换int i = 0;和进入功能添加assert(n != 0);。

基础-10对数的整数

以10为整数对数可以用类似地计算 - 与最大的平方来测试是10 16因为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
}

此已在上面的评价被提出。使用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);
}

我从来没有与你所使用的公式浮点精度的问题（和数字的快速检查1至2 31 - 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; 
}

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

这是不标准或一定便携式的，但它在一般工作的意愿。我不知道它是多么有效。

转换的整数索引的足够的精度一个浮点数。该表示将是精确的，假定的精度是足够的。

查找IEEE浮点数的表示，提取指数，并进行必要的调整，以找到在基座2日志。

如果您使用C ++ 11可以使这一constexpr功能：

constexpr std::uint32_t log2(std::uint32_t n)
{
    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;

此功能确定需要多少位来表示数字间隔：[0..maxvalue] 

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

通过从结果中减去1，将得到floor(log2(x))，其是确切 log2(x)的表示时x是2的幂。

<强> X 的ý 的 Y-1 点击 0 0 -1 结果 <强> 1 1 <强> 0 结果 <强> 2 2 <强> 1 结果 3 2 1 结果 的 4 3 <强> 2 结果 5 3 2 结果 6 3 2 结果 7 3 2 结果 的 8 4 第3 结果

有多深，你投射你的树是？你可以一个范围发言权...... +/- 0.00000001设置数量迫使它为整数值。

我其实并不一定你会打像1.99999999一些，因为你的log 2不该输计算2 ^ n个值（由于浮点回合的最接近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 ;
}

这是一个旧的文章，但我共享一行的算法：

unsigned uintlog2(unsigned x)
{
   unsigned l;
   for(l=0; x>1; x>>=1, l++);
   return l;
}

重写的托德雷曼的回答是更通用的：

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

锵与-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的功率将不会出现错误。精确表示

这确实给一个微不足道而是哈克溶液 - 解释浮点数为整数的比特模式，并且只看指数。这是上述大卫索恩利的溶液。

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位等值。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top