Java 中的位移

Bitshifting in Java

提问by Alexander

I'm trying to understand how bit shift works. Can someone please explain the meaning of this line:

我试图了解位移位的工作原理。有人可以解释一下这行的含义：

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

where nis an integer and give me an example of a nwhen the shift is executed.

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

回答by Jon Hanna

Breaking it down:

分解它：

n & 1will do a binary comparison between n, and 1 which is 00000000000000000000000000000001in binary. As such, it will return 00000000000000000000000000000001when n ends in a 1 (positive odd or negative even number) and 00000000000000000000000000000000otherwise.

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

(n & 1) == 0will hence be true if n is even (or negative odd) and false otherwise.

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

n >> = 1is equivalent to n = n >> 1. As such it shifts all bits to the right, which is roughly equivalent to a division by two (rounding down).

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

If e.g. n started as 12 then in binary it would be 1100. After one loop it will be 110 (6), after another it will be 11 (3) and then the loop will stop.

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

If n is 0 then after the next loop it will still be 0, and the loop will be infinite.

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

回答by codaddict

Lets nbe 4which in binary is represented as:

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

00000000 00000000 00000000 00000100

(n&1)bitwise ands the nwith 1.
1has the binary representation of:

(n&1)按位与n与1.
1具有以下二进制表示：

00000000 00000000 00000000 00000001

The result of the bitwise anding is 0:

按位与运算的结果是0：

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

so the condition of while is true.
Effectively (n&1)was used to extract the least significant bit of the n.

所以 while 的条件为真。
有效地(n&1)用于提取n.

In the while loop you right shift(>>) nby 1. Right shifting a number by kis same as dividing the number by 2^k.

在while循环，你右移（>>）n通过1。将数字右移k与将数字除以 相同2^k。

nwhich is now 00000000 00000000 00000000 00000100on right shifting once becomes 00000000 00000000 00000000 00000010which is 2.

n这是现在00000000 00000000 00000000 00000100的右移位一次变得 00000000 00000000 00000000 00000010这是2。

Next we extract the LSB(least significant bit) of nagain which is 0and right shift again to give 00000000 00000000 00000000 0000001which is 1.

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

Next we again extract LSB of n, which is now 1and the loop breaks.

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

So effectively you keep dividing your number nby 2till it becomes oddas odd numbers have their LSB set.

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

Also note that if nis 0to start with you'll go into an infinite loop because no matter how many times you divide 0by 2you'll not get a odd number.

还要注意的是，如果n是0先从你会进入一个无限循环，因为无论你有多少次划分0由2你不会得到一个奇数。

回答by BlueMonkMN

Assume n = 12. The bits for this would be 1100 (1*8 + 1*4 + 0*2 + 0*1 = 12). The first time through the loop n & 1 == 0 because the last digit of 1100 is 0 and when you AND that with 1, you get 0. So n >>= 1 will cause n to change from 1100 (12) to 110 (6). As you may notice, shifting right has the same effect as dividing by 2. The last bit is still zero, so n & 1 will still be 0, so it will shift right one more time. n>>=1 will cause it to shift one more digit to the right changing n from 110 (6) to 11 (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)。

Now you can see the last bit is 1, so n & 1 will be 1, causing the while loop to stop executing. The purpose of the loop appears to be to shift the number to the right until it finds the first turned-on bit (until the result is odd).

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

回答by haylem

Let's assume equals 42(just because):

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

int n = 42;

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

Iteration 0:

迭代0：

• n = 42(or 0000 0000 0000 0000 0000 0000 0010 1010)
• n & 1 == 0is true(because n&1 = 0 or 0000 0000 0000 0000 0000 0000 0000 0000)

• 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）

Iteration 1:

迭代 1：

• n = 21(or 0000 0000 0000 0000 0000 0000 0001 0101)
• n & 1 == 0is false(because n & 1 == 1or 0000 0000 0000 0000 0000 0000 0000 0001)

• 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）

What it does:

它能做什么：

Basically, you loop divides n by 2 as long as n is an even number:

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

• n & 1 is a simple parity check,
• n >>= 1 shifts the bits to the right, which just divides by 2.

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

回答by haylem

for example if n was

例如，如果 n 是

n=    b11110000

then

然后

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

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

n=    b01111000

if the loop continues it should be

如果循环继续，它应该是

n=    b00001111

回答by Faisal Feroz

n & 1 is actually a bitwise AND operataion. Here the bit pattern of n would be ANDED against the bit pattern of 1. Who's result will be compared against zero. If yes then n is right shifted 1 times. You can take the one right shift as division by 2 and so on.

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