下面的代码 returns 是否给定数字是 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 位，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

2 的幂总是只有一位为“1”：

2⁰ = 1 → 0000 0001
2¹ = 2 → 0000 0010
2² = 4 → 0000 0100
2³ = 8 → 0000 1000

...等等。

任何其他数字将至少有两个“1”位。比如6号是0110，9号是1001等等。

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

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

或者你需要从左边的另一个1借。

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

这意味着实际上，从右边开始的第一个“1”不会出现在结果中，它右边的所有数字都会变成“1”。其左边所有数字不变。

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

2³ = 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”位，结果将为零。

Answer 3

这完全是关于整数值的二进制表示的性质。

在每个位置符号中，相同的符号用于不同的数量级。在二进制表示中，符号 1 根据其位置用于表示 2 的大小。这样，任何整数都可以表示为 2 的幂之和：

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

不难看出，要表示2的一次幂，只需要在相应的位置用一个1的符号即可。所以代码：

num1 & (num1 - 1)

只是检查在值的二进制表示中是否只有 1 位设置为 1。

下面的代码 returns 是否给定数字是 2 的幂。它是如何工作的？

The code below returns whether the given number is a power of two or not. How does it work?

java

bitwise-operators