c - 高效计算 2 的幂

Question

我需要计算k为 2 的最小幂，即 >= 整数值，n（n始终 > 0）

目前我正在使用：

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

k = round(pow(2,(ceil(log2(n)))));

这是一个性能关键的功能

有没有一种计算效率更高的计算方法k？

Answer 1

/* returns greatest power of 2 less than or equal to x, branch-free */
/* Source: Hacker's Delight, First Edition. */
int
flp2(int x)
{
    x = x | (x>>1);
    x = x | (x>>2);
    x = x | (x>>4);
    x = x | (x>>8);
    x = x | (x>>16);
    return x - (x>>1);
}

研究它并看看它是如何工作的很有趣。我认为让您确定您看到的哪种解决方案最适合您的情况的唯一方法是在文本夹具中使用所有这些解决方案并对其进行分析，看看哪种解决方案最适合您的目的。

由于没有分支，相对于其他一些，这可能在性能方面相当不错，但您应该直接对其进行测试以确定。

如果您想要两个大于或等于 X 的最小幂，您可以使用稍微不同的解决方案：

unsigned
clp2(unsigned x)
{
    x = x -1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x + 1;
}

Answer 2

lim = 123;
n = 1;
while( ( n = n << 1 ) <= lim );

将你的数字乘以 2，直到它大于 lim。

左移 1 将值乘以 2。

Answer 3

是的，您可以通过简单地获取相关数字并使用位移来确定 2 的幂来计算这一点。
右移将数字中的所有位移到右侧，丢弃最右边的位（最不重要） 数字。它相当于执行一个整数除以 2。左移一个值将所有位向左移动，删除左端移位的位，并在右端添加零，有效地将值乘以 2。所以如果您计算在数字达到零之前需要右移多少次，您已经计算出以 2 为底的对数的整数部分。然后通过多次左移值 1 来使用它来创建结果。

  int CalculateK(int val)
  {
      int cnt = 0;
      while(val > 0)
      {
           cnt++;
           val = val >> 1;
      }
      return 1 << cnt;
  }

编辑：或者，更简单一点：您不必计算计数

  int CalculateK(int val)
  {
      int res = 1;
      while(res <= val) res <<= 1;
      return res ;
  }

Answer 4

int calculate_least_covering_power_of_two(int x)
{
  int k = 1;
  while( k < x ) k = k << 1;
  return k;
}

Answer 5

k = 1 << (int)(ceil(log2(n)));

您可以利用二进制数字表示 2 的幂的事实（1 是 1，10 是 2，100 是 4，等等）。将 1 左移 2 的指数会得到相同的值，但速度要快得多。

虽然如果你能以某种方式避免 ceil(log2(n)) 你会看到更大的性能提升。

Answer 6

资料来源：hackersdelight.org

/* altered to: power of 2 which is greater than an integer value */

unsigned clp2(unsigned x) {
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

请记住，您需要添加：

x = x | (x >> 32);

对于 64 位数字。