计算快速对数底2上限

Question

在输入和输出都是64位整数的情况下，计算(long int) ceiling(log_2(i))的快速方法是什么？有符号或无符号整数的解决方案是可接受的。我怀疑最好的方法是使用类似于here的方法，而不是尝试我自己的方法，而不是使用已经经过良好测试的方法。一个通用的解决方案将适用于所有正值。

例如，2,3,4,5,6,7,8的值是1,2,2,3,3,3,3

编辑:到目前为止，最好的方法似乎是使用任何数量的快速现有bithack或寄存器方法来计算整数/底对数2(MSB的位置)，然后在输入不是2的幂的情况下添加1。对2的幂的快速逐位检查是(n&(n-1))。

编辑2:关于整数对数和前导零方法的一个很好的来源是Henry S.Warren在Hacker's Delight中的5-3和11-4节。这是我发现的最彻底的治疗方法。

编辑3:这项技术看起来很有前途：https://stackoverflow.com/a/51351885/365478

Answer 1

这个算法已经发布了，但是下面的实现非常紧凑，应该会优化成无分支的代码。

int ceil_log2(unsigned long long x)
{
  static const unsigned long long t[6] = {
    0xFFFFFFFF00000000ull,
    0x00000000FFFF0000ull,
    0x000000000000FF00ull,
    0x00000000000000F0ull,
    0x000000000000000Cull,
    0x0000000000000002ull
  };

  int y = (((x & (x - 1)) == 0) ? 0 : 1);
  int j = 32;
  int i;

  for (i = 0; i < 6; i++) {
    int k = (((x & t[i]) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;
  }

  return y;
}


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  printf("%d\n", ceil_log2(atol(argv[1])));

  return 0;
}

Answer 2

如果您可以将自己限制为gcc，那么有一组内置函数可以返回前导零位的数量，并且可以用来做一些工作来做您想做的事情：

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)

Answer 3

如果你是在Windows的64位处理器上编译，我认为这应该可以工作。_BitScanReverse64是一个内在函数。

#include <intrin.h>
__int64 log2ceil( __int64 x )
{
  unsigned long index;
  if ( !_BitScanReverse64( &index, x ) )
     return -1LL; //dummy return value for x==0

  // add 1 if x is NOT a power of 2 (to do the ceil)
  return index + (x&(x-1)?1:0);
}

对于32位，您可以通过1到2次调用_BitScanReverse来模拟_BitScanReverse64。检查x的高32位，((long*)&x)1，如果需要，然后检查低32位，((long*)&x)。