我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?


当前回答

在标准c++20中,这包含在<bit>中。 答案很简单

#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
    return std::bit_ceil(v);
}

注意: 我给出的解决方案是针对c++,而不是c,我会给出这个问题的答案,但它是这个问题的副本!

其他回答

检查Bit Twiddling Hacks。你需要得到以2为底的对数,然后加上1。32位值的示例:

四舍五入到下一个2的最高次幂 Unsigned int v;//计算32位v的下一个最高次幂2 v -; V |= V >> 1; V |= V >> 2; V |= V >> 4; V |= V >> 8; V |= V >> 16; v + +;

延伸到其他宽度应该是明显的。

g++编译器提供了一个内置函数__builtin_clz,用于计算前导零:

所以我们可以这样做:

int nextPowerOfTwo(unsigned int x) {
  return 1 << sizeof(x)*8 - __builtin_clz(x);
}

int main () {
  std::cout << nextPowerOfTwo(7)  << std::endl;
  std::cout << nextPowerOfTwo(31) << std::endl;
  std::cout << nextPowerOfTwo(33) << std::endl;
  std::cout << nextPowerOfTwo(8)  << std::endl;
  std::cout << nextPowerOfTwo(91) << std::endl;
  
  return 0;
}

结果:

8
32
64
16
128

但请注意,对于x == 0, __builtin_clz return是未定义的。

在x86中,你可以使用sse4位操作指令来提高速度。

//assume input is in eax
mov    ecx,31      
popcnt edx,eax   //cycle 1
lzcnt  eax,eax   //cycle 2
sub    ecx,eax
mov    eax,1
cmp    edx,1     //cycle 3
jle @done        //cycle 4 - popcnt says its a power of 2, return input unchanged
shl    eax,cl    //cycle 5
@done: rep ret   //cycle 5

在c中,您可以使用匹配的intrinsic。

或者无跳转,通过避免跳转导致的错误预测来加快速度,但通过延长依赖链来减慢速度。计时,看看哪种代码最适合您。

//assume input is in eax
mov    ecx,31
popcnt edx,eax    //cycle 1
lzcnt  eax,eax
sub    ecx,eax
mov    eax,1      //cycle 2
cmp    edx,1
mov    edx,0     //cycle 3 
cmovle ecx,edx   //cycle 4 - ensure eax does not change
shl    eax,cl    
@done: rep ret   //cycle 5

如果您想要单行模板。在这里

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>1)>>2)>>4)>>8)>>16); }

or

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }

c#中的可移植解决方案:

int GetNextPowerOfTwo(int input) {
    return 1 << (int)Math.Ceiling(Math.Log2(input));
}

Math.Ceiling(Math.Log2(value))计算2的下一个幂的指数,1 <<通过移位计算实值。

更快的解决方案,如果你有。net Core 3或更高版本:

uint GetNextPowerOfTwoFaster(uint input) {
    return (uint)1 << (sizeof(uint) * 8 - System.Numerics.BitOperations.LeadingZeroCount(input - 1));
}

这将使用system . numbers . bitoperations . leadingzerocount(),如果可用,则使用硬件指令:

https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs

更新:

RoundUpToPowerOf2()即将在。net 6!内部实现与上面的. net Core 3解决方案基本相同。

这里是社区更新。