我可以理解它使用按位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”位,结果将为零。

09-10 12:02
查看更多