今天我需要一个简单的算法来检查一个数字是否是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。
有没有更好的算法?
我一直在看《兰登》的文档。nextInt(int bound)，看到了这段漂亮的代码，它检查参数是否为2的幂，它说(代码的一部分):
if ((bound & -bound) == bound) // ie, bouns is a power of 2
我们来测试一下
for (int i=0; i<=8; i++) {
System.out.println(i+" = " + Integer.toBinaryString(i));
}
>>
0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000
// the left most 0 bits where cut out of the output
for (int i=-1; i>=-8; i--) {
System.out.println(i+" = " + Integer.toBinaryString(i));
}
>>
-1 = 11111111111111111111111111111111
-2 = 11111111111111111111111111111110
-3 = 11111111111111111111111111111101
-4 = 11111111111111111111111111111100
-5 = 11111111111111111111111111111011
-6 = 11111111111111111111111111111010
-7 = 11111111111111111111111111111001
-8 = 11111111111111111111111111111000
你注意到什么了吗?
2次方的数字在正负二进制表示中有相同的位，如果我们做一个逻辑与，我们得到相同的数字:)
for (int i=0; i<=8; i++) {
System.out.println(i + " & " + (-i)+" = " + (i & (-i)));
}
>>
0 & 0 = 0
1 & -1 = 1
2 & -2 = 2
3 & -3 = 1
4 & -4 = 4
5 & -5 = 1
6 & -6 = 2
7 & -7 = 1
8 & -8 = 8
科特林：
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()))
}
