计算快速基数2天花板

Question

什么是计算(long int) ceiling(log_2(i))输入和输出为6​​4位整数的快速方法？有符号或无符号整数的解决方案是可以接受的.我怀疑最好的方法将是一个类似于这里发现的方法,但不是尝试我自己,我想使用已经经过充分测试的东西.一般解决方案适用于所有正值.

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

编辑:到目前为止,最好的路径似乎是使用任意数量的快速现有bithacks或寄存器方法计算整数/楼层日志基数2(MSB的位置),然后如果输入不是幂的话,则添加一个二.对2的幂的快速按位检查是(n&(n-1)).

编辑2:整数对数和前导零方法的一个很好的来源是亨利S.沃伦的Hacker's Delight中的第5-3和11-4节.这是我发现的最完整的治疗方法.

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

Answer 1

如果你可以限制自己使用gcc,那么有一组内置函数可以返回前导零位的数量,可以通过一些工作来做你想做的事情:

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

Answer 2

该算法已经发布,但是以下实现非常紧凑,应该优化为无分支代码.

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 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位,您可以模拟_BitScanReverse64,对_BitScanReverse进行1或2次调用.检查x的高32位,((long*)&x)[1],如果需要,检查低32位((long*)&x)[0].

Answer 4

我所知道的最快方法是使用快速log2向下舍入，在处理向上舍入情况之前和之后组合无条件调整输入值，lg_down()如下所示。

/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
  return 63U - __builtin_clzl(x);
}

/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
  return lg_down(x - 1) + 1;
}

基本上，将 1 添加到舍入结果对于除 2 的精确幂之外的所有值已经是正确的（因为在这种情况下，floor和ceil方法应该返回相同的答案），因此从输入值中减去 1 就足以处理这种情况（它不会改变其他情况的答案）并将其添加到结果中。

这通常比通过明确检查 2 的精确幂（例如，添加一项!!(x & (x - 1))）来调整值的方法略快。它避免了任何比较和条件操作或分支，更可能在内联时更简单，更适合矢量化等。

这依赖于大多数 CPU 使用 clang/icc/gcc 内置功能提供的“计数前导位”功能__builtin_clzl，但其他平台提供了类似的功能（例如，BitScanReverseVisual Studio 中的内在功能）。

不幸的是，很多人返回了错误的答案log(1)，因为这会导致__builtin_clzl(0)基于 gcc 文档的未定义行为。当然，一般的“计数前导零”函数在零处具有完美定义的行为，但是 gcc 内置函数以这种方式定义，因为在 x86 上的 BMI ISA 扩展之前，它会使用本身具有未定义行为的bsr指令。

如果您知道直接lzcnt使用lzcnt内在指令有指令，则可以解决此问题。除了 x86 之外的大多数平台一开始都没有经历过这个bsr错误，并且可能还提供了访问“计数前导零”指令的方法（如果有的话）。

Answer 5

#include "stdafx.h"
#include "assert.h"

int getpos(unsigned __int64 value)
{
    if (!value)
    {
      return -1; // no bits set
    }
    int pos = 0;
    if (value & (value - 1ULL))
    {
      pos = 1;
    }
    if (value & 0xFFFFFFFF00000000ULL)
    {
      pos += 32;
      value = value >> 32;
    }
    if (value & 0x00000000FFFF0000ULL)
    {
      pos += 16;
      value = value >> 16;
    }
    if (value & 0x000000000000FF00ULL)
    {
      pos += 8;
      value = value >> 8;
    }
    if (value & 0x00000000000000F0ULL)
    {
      pos += 4;
      value = value >> 4;
    }
    if (value & 0x000000000000000CULL)
    {
      pos += 2;
      value = value >> 2;
    }
    if (value & 0x0000000000000002ULL)
    {
      pos += 1;
      value = value >> 1;
    }
    return pos;
}

int _tmain(int argc, _TCHAR* argv[])
{    
    assert(getpos(0ULL) == -1); // None bits set, return -1.
    assert(getpos(1ULL) == 0);
    assert(getpos(2ULL) == 1);
    assert(getpos(3ULL) == 2);
    assert(getpos(4ULL) == 2);
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos(1ULL << k);
        assert(pos == k);
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) - 1);
        assert(pos == (k < 2 ? k - 1 : k) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) | 1);
        assert(pos == (k < 1 ? k : k + 1) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) + 1);
        assert(pos == k + 1);
    }
    return 0;
}

Answer 6

使用@egosys提到的gcc builtins,你可以构建一些有用的宏.对于快速粗糙的楼层(log2(x))计算,您可以使用:

#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))

对于类似的ceil(log2(x)),使用:

#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))

后者可以使用更多的gcc特性进一步优化,以避免对内置的双重调用,但我不确定你在这里需要它.

Answer 7

以下代码片段是一种安全且可移植的方法，用于扩展普通 C 方法（例如 @dgobbi 的方法）以在使用支持编译器 (Clang) 编译时使用编译器内部函数。将它放在方法的顶部将导致该方法在可用时使用内置函数。当内置函数不可用时，该方法将回退到标准 C 代码。

#ifndef __has_builtin
#define __has_builtin(x) 0
#endif

#if __has_builtin(__builtin_clzll) //use compiler if possible
  return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1)));
#endif