计算“2 的幂”数使用的幂的最快方法？

问题描述 投票：0回答：6

查找某个数字（即 2 的幂）所使用的 2 的幂的最快方法是什么？

我不太擅长数学，所以我不知道如何最好地描述它。 但该函数看起来与 

x = 2^y
类似，其中 
y
是输出，
x
是输入。 这是一个真值表，如果这有助于解释的话，它会是什么样子。 

0 = f(1)
1 = f(2)
2 = f(4)
3 = f(8)
...
8 = f(256)
9 = f(512)

我已经创建了一个函数来执行此操作，但我担心它不是很有效（或者说不太优雅）。 有没有更简单、更有效的方法来做到这一点？ 我使用它来计算纹理的哪些区域用于缓冲绘制的完成方式，因此对于每个绘制的对象至少调用一次。 这是我到目前为止所做的功能：

uint32 getThePowerOfTwo(uint32 value){
    for(uint32 n = 0; n < 32; ++n){
        if(value <= (1 << n)){
            return n;
        }
    }
    return 32; // should never be called
}
c++ math
6个回答
12
投票

基于woolstar的答案 - 我想知道查找表的二分搜索是否会稍微快一点？ （而且看起来更好看）...

int getThePowerOfTwo(int value) {
    static constexpr int twos[] = {
        1<<0,  1<<1,  1<<2,  1<<3,  1<<4,  1<<5,  1<<6,  1<<7,
        1<<8,  1<<9,  1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15,
        1<<16, 1<<17, 1<<18, 1<<19, 1<<20, 1<<21, 1<<22, 1<<23,
        1<<24, 1<<25, 1<<26, 1<<27, 1<<28, 1<<29, 1<<30, 1<<31
    };

    return std::lower_bound(std::begin(twos), std::end(twos), value) - std::begin(twos);
}
4
投票

此操作非常流行，处理器供应商为此提供了硬件支持。 查看找到第一组。 编译器供应商为此提供了特定的函数，不幸的是似乎没有标准如何命名它。 因此，如果您需要最大性能，则必须创建依赖于编译器的代码：

# ifdef __GNUC__  
    return __builtin_ffs( x ) - 1; // GCC
#endif
#ifdef _MSC_VER
    return CHAR_BIT * sizeof(x)-__lzcnt( x ); // Visual studio
#endif
2
投票

如果输入值仅为

2^n
，其中
n
- 整数，则找到
n
的最佳方法是使用具有完美哈希函数的哈希表。在这种情况下，32 个无符号整数的哈希函数可以定义为 
value % 37

template < size_t _Div >
std::array < uint8_t, _Div > build_hash()
{
    std::array < uint8_t, _Div > hash_;

    std::fill(hash_.begin(), hash_.end(), std::numeric_limits<uint8_t>::max());

    for (size_t index_ = 0; index_ < 32; ++index_)
        hash_[(1 << index_) % _Div] = index_;

    return hash_;
}

uint8_t hash_log2(uint32_t value_)
{
    static const std::array < uint8_t, 37 > hash_ = build_hash<37> ();

    return hash_[value_%37];
}

检查

int main()
{
    for (size_t index_ = 0; index_ < 32; ++index_)
        assert(hash_log2(1 << index_) == index_);   
}
0
投票

您的版本很好，但正如您所猜测的，它的

O(n)
这意味着每一位都需要一步完成循环。 你可以做得更好。 要进入下一步，请尝试进行相当于分而治之的操作：

unsigned int log2(unsigned int value)
{
  unsigned int val = 0 ;
  unsigned int mask= 0xffff0000 ;
  unsigned int step= 16 ;

  while ( value )
  {
    if ( value & mask ) { val += step ;  value &= ~ mask ; }
    step /= 2 ;
    if ( step ) { mask >>= step ; } else { mask >>= 1 ; }
  }

  return val ;
}

由于我们只是寻找最高位，因此我们首先询问字的上半部分是否有任何位。 如果有，我们可以丢弃所有低位，否则我们只是缩小搜索范围。

由于问题被标记为

C++
，这里有一个使用模板的版本，试图找出初始掩码和步骤：

template <typename T>
  T log2(T val)
  {
    T result = 0 ;
    T step= ( 4 * sizeof( T ) ) ;  // half the number of bits
    T mask= ~ 0L - ( ( 1L << ( 4 * sizeof( T )) ) -1 ) ;

    while ( val && step )
    {
      if ( val & mask ) { result += step ;  val >>= step ; }
      mask >>= ( step + 1) / 2 ;
      step /= 2 ; 
    }

    return result ;
  }

虽然任一版本的性能在现代 x86 架构上都将是一个小问题，但这在嵌入式解决方案中对我来说已经出现了，在最后一个案例中，我正在解决与此非常相似的位搜索，甚至是 

O(log N)
对于中断来说太慢了，我们不得不使用分而治之和查表的组合来挤出最后几个周期。

0
投票

如果你知道它确实是二的幂（这很容易验证）， 尝试下面的变体。 完整描述在这里：http://sree.kotay.com/2007/04/shift-registers-and-de-bruijn-sequences_10.html

//table
static const int8 xs_KotayBits[32] =    {
       0,  1,  2, 16,  3,  6, 17, 21,
       14,  4,  7,  9, 18, 11, 22, 26,
       31, 15,  5, 20, 13,  8, 10, 25,
       30, 19, 12, 24, 29, 23, 28, 27
       };


//only works for powers of 2 inputs
static inline int32 xs_ILogPow2 (int32 v){
   assert (v && (v&(v-1)==0));
   //constant is binary 10 01010 11010 00110 01110 11111
   return xs_KotayBits[(uint32(v)*uint32( 0x04ad19df ))>>27];
}
0
投票

因此最快的方法是使用编译器提供的内置函数。但有一些只需要代码的替代方案。

基准（1亿次交互）：

| ------- | unoptimized | optimized |
| loop    | 2.057s      | 0.780s    |
| func1   | 0.749s      | 0.151s    |
| func2   | 0.721s      | 0.000s    |
| builtin | 0.189s      | 0.000s    |

功能1：

unsigned int f1(unsigned int value) {
    unsigned int n1 = 0;
    unsigned int n2 = 1;
    unsigned int n3 = 2;
    unsigned int n4 = 3;
    unsigned int n5 = 4;
    unsigned int n6 = 5;
    unsigned int n7 = 6;
    unsigned int n8 = 7;
    while((1 << n8) < value) {
        n1 += 8;
        n2 += 8;
        n3 += 8;
        n4 += 8;
        n5 += 8;
        n6 += 8;
        n7 += 8;
        n8 += 8;
    }
    if(value <= (1 << n1)) return n1;
    if(value <= (1 << n2)) return n2;
    if(value <= (1 << n3)) return n3;
    if(value <= (1 << n4)) return n4;
    if(value <= (1 << n5)) return n5;
    if(value <= (1 << n6)) return n6;
    if(value <= (1 << n7)) return n7;
    return n8;
}

功能2：

unsigned int f2(unsigned int value) {
    const int v = value;
    if(v <= (1 << 0)) return 0;
    if(v <= (1 << 1)) return 1;
    if(v <= (1 << 2)) return 2;
    if(v <= (1 << 3)) return 3;
    if(v <= (1 << 4)) return 4;
    if(v <= (1 << 5)) return 5;
    if(v <= (1 << 6)) return 6;
    if(v <= (1 << 7)) return 7;
    if(v <= (1 << 8)) return 8;
    if(v <= (1 << 9)) return 9;
    if(v <= (1 << 10)) return 10;
    if(v <= (1 << 11)) return 11;
    if(v <= (1 << 12)) return 12;
    if(v <= (1 << 13)) return 13;
    if(v <= (1 << 14)) return 14;
    if(v <= (1 << 15)) return 15;
    if(v <= (1 << 16)) return 16;
    if(v <= (1 << 17)) return 17;
    if(v <= (1 << 18)) return 18;
    if(v <= (1 << 19)) return 19;
    if(v <= (1 << 20)) return 20;
    if(v <= (1 << 21)) return 21;
    if(v <= (1 << 22)) return 22;
    if(v <= (1 << 23)) return 23;
    if(v <= (1 << 24)) return 24;
    if(v <= (1 << 25)) return 25;
    if(v <= (1 << 26)) return 26;
    if(v <= (1 << 27)) return 27;
    if(v <= (1 << 28)) return 28;
    if(v <= (1 << 29)) return 29;
    if(v <= (1 << 30)) return 30;
    return 31;
}

是的。这些函数看起来……呃很奇怪。这两个函数都是这样写的，这样CPU就可以同时执行多行代码。函数 2 似乎通过编译器优化效果更好。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.