今天我需要一个简单的算法来检查一个数字是否是2的幂。
该算法需要:
简单的
适用于任何ulong值。
我想出了这个简单的算法:
private bool IsPowerOfTwo(ulong number)
{
if (number == 0)
return false;
for (ulong power = 1; power > 0; power = power << 1)
{
// This for loop used shifting for powers of 2, meaning
// that the value will become 0 after the last shift
// (from binary 1000...0000 to 0000...0000) then, the 'for'
// loop will break out.
if (power == number)
return true;
if (power > number)
return false;
}
return false;
}
但后来我想:如何检查log2x是否恰好是一个整数呢?当我检查2^63+1时,Math.Log()因为四舍五入而返回恰好63。我检查了2的63次方是否等于原来的数,结果是正确的,因为计算是双倍的,而不是精确的数字。
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
这对于给定的错误值返回true: 9223372036854775809。
有没有更好的算法?
在C中,我测试了I && !(I & (I - 1)技巧,并将其与__builtin_popcount(I)进行比较,在Linux上使用gcc,使用-mpopcnt标志,以确保使用CPU的POPCNT指令。我的测试程序计算了0到2^31之间2的幂的整数个数。
起初,我认为I && !(I & (I - 1)快10%,即使我验证了在我使用__builtin_popcount的反汇编中使用了POPCNT。
然而,我意识到我已经包含了一个if语句,分支预测可能在位旋转版本上做得更好。我删除了if和POPCNT,结果更快,正如预期的那样。
结果:
英特尔(R)酷睿(TM) i7-4771 CPU最大3.90GHz
Timing (i & !(i & (i - 1))) trick
30
real 0m13.804s
user 0m13.799s
sys 0m0.000s
Timing POPCNT
30
real 0m11.916s
user 0m11.916s
sys 0m0.000s
AMD Ryzen Threadripper 2950X 16核处理器最大3.50GHz
Timing (i && !(i & (i - 1))) trick
30
real 0m13.675s
user 0m13.673s
sys 0m0.000s
Timing POPCNT
30
real 0m13.156s
user 0m13.153s
sys 0m0.000s
请注意,这里英特尔的CPU似乎比AMD的比特旋转稍慢,但有一个更快的POPCNT;AMD的POPCNT没有提供这么多的提升。
popcnt_test.c:
#include "stdio.h"
// Count # of integers that are powers of 2 up to 2^31;
int main() {
int n;
for (int z = 0; z < 20; z++){
n = 0;
for (unsigned long i = 0; i < 1<<30; i++) {
#ifdef USE_POPCNT
n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
#else
n += (i && !(i & (i - 1))); // Was: if (i && !(i & (i - 1))) n++;
#endif
}
}
printf("%d\n", n);
return 0;
}
运行测试:
gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe
echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe
echo
echo "Timing POPCNT"
time ./test-opt.exe
如果一个数字只包含1个设置位,则它是2的幂。我们可以使用这个属性和泛型函数countSetBits来判断一个数字是否是2的幂。
这是一个c++程序:
int countSetBits(int n)
{
int c = 0;
while(n)
{
c += 1;
n = n & (n-1);
}
return c;
}
bool isPowerOfTwo(int n)
{
return (countSetBits(n)==1);
}
int main()
{
int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
return 0;
}
我们不需要显式地检查0是否是2的幂,因为它对0也返回False。
输出
Num:0 Set Bits:0 is power of two: 0
Num:1 Set Bits:1 is power of two: 1
Num:2 Set Bits:1 is power of two: 1
Num:3 Set Bits:2 is power of two: 0
Num:4 Set Bits:1 is power of two: 1
Num:5 Set Bits:2 is power of two: 0
Num:15 Set Bits:4 is power of two: 0
Num:16 Set Bits:1 is power of two: 1
Num:22 Set Bits:3 is power of two: 0
Num:32 Set Bits:1 is power of two: 1
Num:38 Set Bits:3 is power of two: 0
Num:64 Set Bits:1 is power of two: 1
Num:70 Set Bits:3 is power of two: 0