2的幂次方的高效计算方法

Question

我有一个需求，需要计算k，使其成为大于等于整数n的最小2的幂次方（n始终大于0）。

目前我正在使用以下方法：

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

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

这是一个性能关键的函数。

有没有更加计算效率更高的方式来计算 k？

- bph

---

如果您正在使用GCC编译器，可以使用1 << CHAR_BIT * sizeof x - __builtin_clz(x)，前提是x具有无符号整型或在普通系统上为int类型。对于unsigned long类型，还有一个名为__builtin_clzl的函数。某些非GCC编译器也支持此扩展功能。在拥有“查找第一个位设置”指令的处理器上，这将比迄今为止提供的任何其他答案更快。 - Eric Postpischil

请注意将“>整数值”更改为“>=整数值”。 - bph

现在每个人都必须再次更改他们的答案。 :-) - Eric Postpischil

要求一个堆栈溢出的“撤销”按钮... - bph

与答案无关，但值得提醒任何不了解的人：在类似这样的计算中，放弃+0.5和（int）强制转换是明智的，而是使用floor()或ceiling()函数。当然，对数仍然很慢。 - DarenW

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);
}

研究IT技术相关内容并了解其工作原理很有趣。我认为，想要确定哪种解决方案最适合您的情况，唯一的方法是在文本夹具中使用所有解决方案进行测试，并对其进行分析，看哪种方案最有效。

由于不涉及分支，这个方案相对于其他方案可能性能更好，但您应该直接测试以确保。

如果您想要大于或等于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;
}

- Randy Howard

---

这很好，因为“最左边”的1是答案，目标是将所有其他位都变为0，这样做非常好。对于64位数字，您需要额外的一行代码。 - user2180519

是的。将最终结果上移或下移一次二的幂（取决于实际意图）是相当简单的。希望 Hiett 能够将这些信息用于其程序的特定需求。 - Randy Howard

我想问一下，这些“黑客乐趣”解决方案是否不太可移植，即32位和64位架构？ - bph

我猜需要检查sizeof(unsigned int)吗？ - bph

@Hiett 既然将 0 进行右移仍是 0，如果你需要为 32 位和 64 位都考虑到，那么可以添加额外的一行。32 位的结果仍然是正确的，只会浪费一些指令。 - Rune FS

Answer 2

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

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

左移一位将值乘以2。

- user1944441

---

@EricPostpischil 感谢您的注意，已修复...（对于lim = zero无法工作，但可以使用if()解决） - user1944441

Answer 3

可以通过简单地将数字进行位移操作来计算它的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 ;
  }

- Charles Bretana

Answer 4

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

- Alex Shesterov

---

用不含分支的版本来进行基准测试，我怀疑你会发现这并不是最有效的方法。但是，它可以工作。 - Randy Howard

@RandyHoward 我已经尝试过了，对于我的应用程序没有明显的区别，所以我认为我会坚持使用这个答案，因为它更简单。 - bph

@Randy：这种朴素的方法非常容易理解，但不应该移植到64位（128位等）机器上。首先理解它，然后再转向无分支版本会很有帮助。对于均匀分布的32位整数，无分支版本肯定更高效，但对于小整数可能会稍微慢一些。此外，我已经给你的帖子点了一个“+1”，而且我的帖子被接受了，这是一个很好的惊喜。 - Alex Shesterov

@alex-shesterov，您能解释一下将您的函数移植到64位机器上的问题吗？ - bph

@Hiett：这个答案中的函数适用于16位、32位、64位等任何位数的系统，无需进行任何更改；在最坏情况下，它的复杂度（迭代次数）与系统位数相等（即16位、32位、64位或其他位数）- 也就是说，它在位数上是线性的。RandyHoward答案中的函数需要通过添加x |= x>>32来适应64位平台，并且其复杂度在最坏情况和最好情况下都是对数级别的。我的估计是，在32位系统上，RandyHoward的函数比这个函数平均快15%。 - Alex Shesterov

@alex-shesterov 感谢您的澄清 - 通常我的x值很小，<50。我认为这也许是为什么我在这两个函数之间看不到太大性能差异的原因。然而，在纸上完成了一些clp2示例后，我可以看到它非常优雅。 - bph

Answer 5

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

你可以利用二进制数字表示2的幂次方（1是1，10是2，100是4等）。将1左移2的指数会给你相同的值，但速度更快。

虽然如果你能在某种程度上避免ceil(log2(n))，你会看到更大的性能提升。

- Zach

---

这段代码无法编译，因为 ceil 的类型为 double，不能与 << 一起使用。当插入一个 int 强制转换并且 n 为32时，此代码会产生32，但期望的结果是64。 - Eric Postpischil

我在示例中添加了一个int类型的转换。我不确定为什么n=32时期望的结果会是64...也许我没有理解原始问题。 - Zach

@EricPostpischil，它似乎要求大于或等于n的最小2的幂。32等于32。但也许我仍然误解了。无论如何，Randy Howard的答案更好。 - Zach

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位数字。

- user2180519