Java 中的位移

Question

我试图了解位移位是如何工作的。有人可以解释一下这行的含义吗：

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

其中n是一个整数，并给我一个执行移位时n的例子。

Answer 1

分解：

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

因此，如果 n 为偶数（或负奇数），则 (n & 1) == 0 将为 true，否则为 false。

n>> = 1 相当于 n = n >>> 1..因此，它将所有位向右移动，这大致相当于除以二（向下舍入）。

例如，如果 n 开始为 12，那么在二进制中它将是 1100。在一个循环之后它将是 110 (6)，在另一循环之后它将是 11 (3)，然后循环将停止。

如果n为0，那么下一次循环后它仍然是0，并且循环将是无限的。

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 的条件为 true。
实际上，(n&1) 用于提取 n 的最低有效位。

在 while 循环中，您将 (>>) n 右移 1。将数字右移 k 与将数字除以 2^k 相同。

n 现在右移后变为 00000000 00000000 00000000 00000100
00000000 00000000 00000000 00000010，即2。

接下来，我们再次提取n的LSB（最低有效位），即0，并再次右移得到00000000 00000000 00000000 0000001，即<代码>1。

接下来，我们再次提取 n 的 LSB，现在是 1 并且循环中断。

因此，您可以有效地将数字n除以2，直到它变为奇数，因为奇数已设置其LSB。

另请注意，如果 n 一开始就是 0，您将进入无限循环，因为无论您将 0 除以 < 多少次code>2 你不会得到奇数。

Answer 3

假设 n = 12。其位数为 1100 (1*8 + 1*4 + 0*2 + 0*1 = 12)。
第一次通过循环 n & 1 == 0 因为 1100 的最后一位数字是 0，当你将它与 1 相与时，你会得到 0。所以 n >>= 1 将导致 n 从 1100 (12) 变为 110 (6)。您可能会注意到，右移与除以 2 具有相同的效果。
最后一位仍然为零，因此 n & 1仍然是0，所以会再右移一次。 n>>=1 将导致它向右再移动一位数字，将 n 从 110 (6) 更改为 11 (3)。

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

Answer 4

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

int n = 42;

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

迭代 0:

• n = 42 （或 0000 0000 0000 0000 0000 0000 0010 1010< /code>)
• 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 是偶数，您就循环将 n 除以 2：

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

Answer 5

例如，如果 n 是

n=    b11110000

那么

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

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

n=    b01111000

如果循环继续它应该是

n=    b00001111

Answer 6

n & 1实际上是按位与运算。这里，n 的位模式将与 1 的位模式进行 ANDED。Who 的结果将与 0 进行比较。如果是，则 n 右移 1 次。您可以将右移一位视为除以 2，依此类推。