今天我需要一个简单的算法来检查一个数字是否是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。
有没有更好的算法?
以下对已接受答案的补充可能对某些人有用:
2的幂,当用二进制表示时,总是像1后面跟着n个0,其中n大于等于0。例:
Decimal Binary
1 1 (1 followed by 0 zero)
2 10 (1 followed by 1 zero)
4 100 (1 followed by 2 zeroes)
8 1000 (1 followed by 3 zeroes)
. .
. .
. .
等等。
当我们把这些数减1,它们就变成0后面跟着n个1,同样,n和上面一样。例:
Decimal Binary
1 - 1 = 0 0 (0 followed by 0 one)
2 - 1 = 1 01 (0 followed by 1 one)
4 - 1 = 3 011 (0 followed by 2 ones)
8 - 1 = 7 0111 (0 followed by 3 ones)
. .
. .
. .
等等。
说到关键
当我们对一个数字x做位与运算时会发生什么,x是a
2的幂,x - 1呢?
x的1与x - 1的0对齐,x的所有0与x - 1的1对齐,导致按位and的结果为0。这就是为什么上面提到的单行答案是正确的。
进一步增加了上述公认答案的美感
所以,我们现在有一个属性可供我们使用:
当我们用任何数减去1时,那么在二进制表示法中,最右边的1将变成0,而最右边1左边的所有0也将变成1。
这个性质的一个很棒的用途是求出一个给定数字的二进制表示中有多少个1 ?对于给定的整数x,简短而甜蜜的代码是:
byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);
从上面解释的概念可以证明数字的另一个方面是“每个正数都可以表示为2的幂的和吗?”
是的,每一个正数都可以表示成2的幂的和。对于任何数字,取其二进制表示。乘117路车。
The binary representation of 117 is 1110101
Because 1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have 117 = 64 + 32 + 16 + 0 + 4 + 0 + 1
解决这个问题有一个简单的技巧:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
注意,这个函数对于0报告为真,因为0不是2的幂。如果你想排除这种情况,以下是方法:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
解释
首先,MSDN定义中的按位二进制&运算符:
二进制和操作符是为整型和bool类型预定义的。为
整型,&计算其操作数的逻辑位与。
对于bool操作数,&计算其操作数的逻辑与;那
Is,当且仅当它的两个操作数都为真时,结果为真。
现在让我们来看看这一切是如何发生的:
该函数返回布尔值(true / false),并接受一个unsigned long类型的传入参数(在本例中为x)。为了简单起见,让我们假设有人传递了值4,并像这样调用函数:
bool b = IsPowerOfTwo(4)
现在我们将x的每一次出现都替换为4:
return (4 != 0) && ((4 & (4-1)) == 0);
我们已经知道4 != 0的值为真,到目前为止还不错。但是:
((4 & (4-1)) == 0)
当然,这可以转化为:
((4 & 3) == 0)
但是4和3到底是什么呢?
4的二进制表示是100,3的二进制表示是011(记住&取这些数字的二进制表示)。所以我们有:
100 = 4
011 = 3
想象一下这些值像基本加法一样堆积起来。&运算符表示,如果两个值都等于1,则结果为1,否则为0。1 & 1 = 1,1 & 0 = 0,0 & 0 = 0, 0 & 1 = 0。我们来算算:
100
011
----
000
结果就是0。所以我们回过头来看看return语句现在转换成了什么:
return (4 != 0) && ((4 & 3) == 0);
现在翻译过来就是:
return true && (0 == 0);
return true && true;
我们都知道true && true就是true,这表明在我们的例子中,4是2的幂。
科特林:
fun isPowerOfTwo(n: Int): Boolean {
return (n > 0) && (n.and(n-1) == 0)
}
or
fun isPowerOfTwo(n: Int): Boolean {
if (n == 0) return false
return (n and (n - 1).inv()) == n
}
Inv对该值中的位进行反转。
注意:
Log2解决方案不适用于较大的数字,如536870912 ->
import kotlin.math.truncate
import kotlin.math.log2
fun isPowerOfTwo(n: Int): Boolean {
return (n > 0) && (log2(n.toDouble())) == truncate(log2(n.toDouble()))
}
在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