Bitshifting Java, please explain

Question

Hi!

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 n is an integer and give me an example of a n when the shift is executed.

Thanks!

Answer 1

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).

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).

Answer 2

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.

Answer 3

Breaking it down:

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

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

n >> = 1 is 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).

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.

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

Answer 4

for example if n was

n=    b11110000

then

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

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

n=    b01111000

if the loop continues it should be

n=    b00001111

Answer 5

Lets n be 4 which in binary is represented as:

00000000 00000000 00000000 00000100

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

00000000 00000000 00000000 00000001

The result of the bitwise anding is 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.

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

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

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

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

So effectively you keep dividing your number n by 2 till it becomes odd as odd numbers have their LSB set.

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

Answer 6

Let's assume equals 42 (just because):

int n = 42;

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

Iteration 0:

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

Iteration 1:

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

What it does:

Basically, you loop divides n by 2 as long as n is an odd number (and will possibly loop indefinitely for numbers that are powers of 2):

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

Careful: Things that could get awry, because:

• it will work only on integers (as in, it will do something on other numbers, but not the same thing),
• if your number is, say 4, then you're in an infinite loop because n will be divided to 2, then 0 and then that's it you'll be stuck on 0 forever (because right-most bits are not transferred back to the left-most bits).