我可以理解它使用按位AND运算符,但是它如何工作?
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long num1=sc.nextLong();
long count=(num1 & (num1- 1));
if(count == 0l) {
System.out.println("power of two");
}
}
最佳答案
2的幂总是只有一位,即“ 1”:
20 = 1→0000 0001
21 = 2→0000 0010
22 = 4→0000 0100
23 = 8→0000 1000
... 等等。
任何其他数字将至少具有两个“ 1”位。例如,数字6为0110,数字9为1001,依此类推。
如果从数字中减去1,则您在最右边的位置将有1:
00000101
-00000001
────────
00000100
否则您需要向左再借1个。
00010100
-00000001
────────
00010011
这意味着有效的是,从右数起的第一个“ 1”将不会出现在结果中,其右数位的所有数字都将变为“ 1”。其左侧的所有数字均保持不变。
因此,如果初始数字中只有一个“ 1”(即2的幂),那么我们将在1处有0。使用&
,您将获得:
23 = 8→0000 1000
-1→0000 0111
&8→0000 0000&
之后,原始8中所有为零的位将为零。我们知道,减法会将第一个“ 1”放在零处。这样在&
之后也将变为零。结果:整数为零。
但是,如果该数字不是2的幂,则在减法借用的数字的左边还有一个“ 1”位。 “ 1”位不会改变:
24→0001 1000
-1→0001 0111
&24→0001 0000
一直到第一个原始“ 1”的右侧现在为零。但是,正如我们注意到的那样,第一个“ 1”左侧的位没有更改,没有借用。因此,当您在左侧的位上执行&
时,结果仍然为“ 1”。
因此,这种情况下的结果将不会为零。
因此,当您执行n & (n-1)
时,如果n
不是2的幂,则您将有一个以上的“ 1”位,并且结果为非零。如果是2的幂,则只有1个“ 1”位,结果将为零。