下面的代码返回给定的数字是否为2的幂.它是如何工作的

Question

我可以理解它使用了位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");
  }
}

Answer 1

如果num是2的幂，则num & (num1 -1)为0，因为num-1将具有1位，其中num具有0位，而num具有1位。

如果num是2的幂，则它具有单个1位：

num           00..00100000000..00
num-1         00..00011111111..11
num & (num-1) 00..00000000000..00

如果num不是2的幂，则在num中至少有两个1比特。如果你检查它们中的第一个和最后一个，你会得到：

num           00..001xx..xxx10..0
num-1         00.0001xx..xxx01..1
num & (num-1) 00.0001xx..xxx00..0

因此num & (num-1)至少具有一个1比特。

Answer 2

二的幂总是只有一个位是"1"：

20=1→0000 000121=2→0000 001022=4→0000 010023=8→0000 1000

等等

任何其他数字都将至少有两个"1"位。例如，数字6是0110，数字9是1001等等

当你从一个数字中减去一时，要么你在最右边的位置有1：

00000101-00000001────────00000100

否则你需要向左边的另一个1借。

00010100-00000001────────00010011

这意味着，从右边开始的第一个"1"将不在结果中，并且它右边的所有数字都将变为"1"。它左边的所有数字都没有变化。

因此，如果最初的数字中只有一个"1"——它是2的幂——那么1所在的位置将为0。使用&，您得到的是：

23=8→0000 1000-1→0000 0111&8→0000 0000

在CCD_ 11之后，在原始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"位，结果为零。

Answer 3

这一切都是关于整数值的二进制表示的性质。

在每个位置记法中，相同的符号用于不同的数量级。在二进制表示中，符号CCD_ 16用于取决于其位置的CCD_。这样，任何整数都可以表示为2:的幂和

5₁₀=101₂=1*2²+0*2¹+1*2⁰

不难看出，为了表示CCD_ 18的功率，在相应位置仅需要CCD_ 19的一个符号。所以代码：

num1 & (num1 - 1)

简单地检查在该值的二进制表示中只有1个比特被设置为CCD_ 20。