0

我需要计算 2 的最大幂，它 < 一个整数值，x

目前我正在使用：

#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)

x = round(pow(2,(ceil(log2(n))-1)));

这是一个性能关键的功能

是否有计算 x 的计算效率更高的方法？

4

6 回答 6

3

您实际上是在寻找数字中最高的非零位。许多处理器为此内置了指令，而这些指令又被许多编译器公开。例如，在 GCC 中，我会查看__builtin_clz，

返回 中前导 0 位的数量x，从最高有效位位置开始。

与sizeof(int) * CHAR_BIT移位一起，您可以使用它来计算相应的纯二次幂整数。还有一个长整数版本。

（CPU 指令大概称为“CLZ”（计算前导零），以防您需要为其他编译器查找它。）

于 2013-04-14T17:09:04.457 回答
2

基于Bit Twiddling Hacks：在Sean Eron Anderson的 O(lg(N)) 运算中找到 N 位整数的以 2 为底的对数（代码由 Eric Cole 和 Andrew Shapira 提供）：

unsigned int highest_bit (uint32_t v) {
    unsigned int r = 0, s;
    s = (v > 0xFFFF) << 4; v >>= s; r |= s;
    s = (v > 0xFF  ) << 3; v >>= s; r |= s;
    s = (v > 0xF   ) << 2; v >>= s; r |= s;
    s = (v > 0x3   ) << 1; v >>= s; r |= s;
    return r | (v >> 1);
}

这将返回输入最高位的索引；不大于输入的 2 的最大幂是 then 1 << highest_bit(x)，因此严格小于输入的 2 的最大幂是简单的1 << highest_bit(x-1)。

对于 64 位输入，只需将输入类型更改为uint64_t并在函数开头的变量声明之后添加以下额外行：

    s = (v > 0xFFFFFFFF) << 8; v >>= s; r |= s;
于 2013-04-14T17:32:48.947 回答
2

我的 c-libutl 库中有一个整数 log2 函数（如果有人感兴趣，则托管在 googlecode 上）

/*
** Integer log base 2 of a 32 bits integer values.
**   llog2(0) == llog2(1) == 0
*/
unsigned short llog2(unsigned long x)
{
  long l = 0;

  x &= 0xFFFFFFFF /* just in case 'long' is more than 32bit */

  if (x==0) return 0;

  #ifndef UTL_NOASM
    #if defined(__POCC__) || defined(_MSC_VER) || defined (__WATCOMC__)
        /* Pelles C            MS Visual C++         OpenWatcom */
      __asm { mov eax, [x]
              bsr ecx, eax
              mov  l, ecx
      }
    #elif defined(__GNUC__)
      l = (unsigned short) ((sizeof(long)*8 -1) - __builtin_clzl(x));
    #else
      #define UTL_NOASM
    #endif  
  #endif

  #ifdef UTL_NOASM  /* Make a binary search.*/
    if (x & 0xFFFF0000) {l += 16; x >>= 16;} /* 11111111111111110000000000000000 */
    if (x & 0xFF00)     {l += 8;  x >>= 8 ;} /* 1111111100000000*/
    if (x & 0xF0)       {l += 4;  x >>= 4 ;} /* 11110000*/
    if (x & 0xC)        {l += 2;  x >>= 2 ;} /* 1100 */
    if (x & 2)          {l += 1;  }          /* 10 */
    return l;
  #endif

  return (unsigned short)l;
}

然后你可以简单地计算

 (1 << llog2(x))

计算小于 x 的 2 的最大幂。小心0！你应该分开处理。

它使用汇编代码，但也可以通过定义 UTL_NOASM 符号强制使用纯 C 代码。

该代码当时已经过测试，但我已经有一段时间没有使用它了，我不能说它是否在 64 位环境中运行。

于 2013-04-14T17:35:19.067 回答
0

移动位很可能会快得多。可能一些对位的二等分方法可以使其更快。很好的锻炼来改善。

#include <stdio.h>

int closestPow2(int x)
{
        int     p;

        if (x <= 1) return 0; /* No such power exists */

        x--;   /* Account for exact powers of 2, then one power less must be returned */
        for (p = 0; x > 0; p++)
        {
                x >>= 1;
        }

        return 1<<(p-1);
}

int main(void)
{
        printf("%x\n", closestPow2(0x7FFFFFFF));
        return 0;
}
于 2013-04-14T17:05:46.930 回答
0

左右移位运算符做得最好

int MaxPowerOf2(int x)
{
   int out = 1;
   while(x > 1) { x>>1; out<<1;}
   return out;
}
于 2013-04-14T17:08:39.920 回答
0 
#include <math.h>  

double greatestPower( double x )  
{  
    return floor(log( x ) / log( 2 ));  
}

这是真的，因为log在单调递增函数中。

于 2013-04-14T17:11:45.437 回答