Java中的位移操作

Question

我正试图理解位移操作的原理。请问有人可以解释一下以下代码的意义吗？

我正在尝试理解位移操作的工作原理。请问有人能够解释一下以下代码的含义吗？

while ((n&1)==0) n >>= 1;

其中n是一个整数，请给出一个执行移位操作时的n的示例。

- Alexander

Answer 1

分解一下：

n & 1 将对 n 和 1 进行二进制比较，其中1的二进制表示为00000000000000000000000000000001。因此，当n以1结尾（即正奇数或负偶数）时，它将返回00000000000000000000000000000001，否则返回00000000000000000000000000000000。

(n & 1) == 0 对于偶数（或负奇数）返回 true，其他情况返回 false。

n >> = 1 等同于 n = n >> 1。它将所有位向右移动，大致相当于除以2（向下取整）。

例如，如果 n 开始为 12，则在二进制中为 1100。经过一次循环后，它将变为 110（6），再经过一次循环将变为 11（3），然后循环将停止。

如果 n 为0，则在下一次循环之后仍将保持为0，并且循环将是无限的。

- Jon Hanna

---

回滚，因为我认为对于前几个案例，拥有完整的大小是值得的，尽管在那之后我进行了缩短。 - Jon Hanna

非常感谢！这就是我喜欢这个网站的原因，只需几分钟就能得到很好的答案 :) 让我们继续编码... - Alexander

答案部分不正确：负偶数的最后一位也等于零，因此 (n & 1) == 0 对于正偶数和负偶数都是正确的。 - Ilya

Answer 2

假设 n 为 4，用二进制表示为：

00000000 00000000 00000000 00000100

(n&1) 位运算符将 n 和 1 进行按位与操作。
1 的二进制表示为：

00000000 00000000 00000000 00000001

按位与的结果是0：

00000000 00000000 00000000 00000100 = n
00000000 00000000 00000000 00000001 = 1
------------------------------------
00000000 00000000 00000000 00000000 = 0

所以while循环的条件为真。实际上，(n&1)被用于提取n的最低有效位。

在while循环中，通过将n右移1位来进行循环。将一个数向右移动k位相当于将该数除以2^k。

现在n为00000000 00000000 00000000 00000100，右移一位后变成了00000000 00000000 00000000 00000010，即2。

接下来，我们再次提取n的最低有效位，即0，并再次右移，得到00000000 00000000 00000000 0000001，这是1。

接下来，我们再次提取n的最低有效位，此时为1，循环终止。

因此，你将保持将n除以2，直到它成为奇数，因为奇数具有其最低有效位设置。

还要注意，如果n从开始就是0，则会进入无限循环，因为无论你将0除以2多少次，你都不会得到一个奇数。

- codaddict

Answer 3

假设 n = 12。对应的二进制位为1100（1*8 + 1*4 + 0*2 + 0*1 = 12）。 第一次循环时，n & 1 == 0，因为1100的最后一位是0，当你将其与1进行AND运算时，得到0。所以n >>= 1会导致n从1100（12）变为110（6）。正如您所注意到的，向右移位具有除以2的相同效果。 最后一位仍然是零，所以n & 1仍然是0，所以它会再次向右移动一位。n >>= 1会导致它再向右移动一位，将n从110（6）更改为11（3）。

现在您可以看到最后一位是1，因此n & 1将为1，导致while循环停止执行。循环的目的似乎是将数字向右移位，直到找到第一个打开的位（直到结果为奇数）。

- BlueMonkMN

---

哎呀，第一次看的时候我没看到作业标签。这个信息太多了吗？ - BlueMonkMN

Answer 4

假设等于42（只是因为）：

int n = 42;

while ((n & 1) == 0) {
  n >>= 1;
}

迭代0：

• n = 42（或0000 0000 0000 0000 0000 0000 0010 1010）
• n & 1 == 0 是true（因为n&1 = 0，或0000 0000 0000 0000 0000 0000 0000 0000）

迭代1：

• n = 21（或0000 0000 0000 0000 0000 0000 0001 0101）
• n & 1 == 0 是false（因为n & 1 == 1或0000 0000 0000 0000 0000 0000 0000 0001）

它的作用：

基本上，循环将n除以2，只要n是偶数：

• n & 1是一个简单的奇偶校验，
• n >>= 1向右移位，这只是除以2。

- haylem

Answer 5

例如，如果 n 是

n=    b11110000

那么

n&1=  b11110000 &
      b00000001 
      ---------
      b00000000

n>>=1 b11110000 >> 1
      ---------
      b01111000

n=    b01111000

如果循环继续，应该是这样的。

n=    b00001111

- user295190

Answer 6

n & 1 实际上是一个按位与操作。这里，n 的位模式将与 1 的位模式进行 AND 运算。其结果将与零进行比较。如果是，则 n 将向右移动 1 次。您可以将一个右移视为除以 2 等等。

- Faisal Feroz