15

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

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

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

4

6 回答 6

21

分解它：

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

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

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

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

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

于 2010-10-10T17:11:47.123 回答
10

让我们n在4二进制中表示为：

00000000 00000000 00000000 00000100

(n&1)按位与nwith 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。

nwhich is now 00000000 00000000 00000000 00000100on right shift 一旦变为 00000000 00000000 00000000 00000010which is 2。

接下来我们再次提取哪个是的LSB（最低有效位）并n再次0右移以给出00000000 00000000 00000000 0000001哪个是1。

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

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

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

于 2010-10-10T17:21:21.900 回答
4

假设 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 的效果相同。最后一位仍为 0，因此 n & 1 仍为 0，因此它会再右移一次。n>>=1 将导致它向右移动一位数字，将 n 从 110 (6) 更改为 11 (3)。

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

于 2010-10-10T17:10:24.100 回答
2

让我们假设等于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 是偶数，您就可以将 n 除以 2：

  • n & 1 是一个简单的奇偶校验，
  • n >>= 1 将位向右移动，仅除以 2。
于 2010-10-10T18:04:23.133 回答
1

例如，如果 n 是

n=    b11110000

然后

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

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

n=    b01111000

如果循环继续，它应该是

n=    b00001111
于 2010-10-10T17:14:49.713 回答
0

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

于 2010-10-10T17:10:52.073 回答