Bitshifting in Java

Question

I am trying to understand how a bit shift works. Can someone explain the meaning of this line:

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

where n is an integer and gives me an example a n when the shift is performed.

Answer 1

Destruction:

n & 1 will perform a binary comparison between n and 1, which is 00000000000000000000000000000000000000 in binary format. So it will return 00000000000000000000000000000001 when n ends with 1 (positive odd or negative even number) and 0000000000000000000000000000000000000000 otherwise.

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

n >> = 1 equivalent to n = n >> 1 . Thus, it shifts all bits to the right, which is roughly equivalent to dividing by two (rounding).

If, for example, n started as 12, then in binary it will be 1100. After one cycle it will be 110 (6), after another it will be 11 (3), and then the cycle will stop.

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

Answer 2

Allows n be 4 , which in binary format is represented as:

 00000000 00000000 00000000 00000100 

(n&1) bitwise, and n with 1 .
1 has a binary representation:

 00000000 00000000 00000000 00000001 

Bitwise Result 0 :

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

therefore, the while condition is true.
Effectively (n&1) used to extract the least significant digit n .

In a while loop, you shift right ( >> ) n by 1 . The right shift of the number by k coincides with the division of the number by 2^k .

n , which is now 00000000 00000000 00000000 00000100 with a right offset, once becomes 00000000 00000000 00000000 00000010 , which is 2 .

Then we again extract the least significant bit of the least significant bit n , which is 0 and the right shift to give 00000000 00000000 00000000 0000001 , which is 1 .

Then we again retrieve the LSB from n, which is now 1 , and the loop breaks.

Thus, you continue to divide the number n by 2 until it becomes odd , since the odd numbers have their own LSB set.

Also note that if n is 0 for starters, you will go into an infinite loop, because no matter how many times you divide 0 by 2 , you will not get an odd number.

Answer 3

Assume that n = 12. The bits for this will be 1100 (1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 = 12). The first time through the cycle n and 1 == 0, because the last digit 1100 is 0, and when you And that from 1, you get 0. So n → = 1 will lead to a change in n from 1100 (12) to 110 (6 ) As you can see, shifting to the right has the same effect as dividing by 2. The last bit is still zero, so n and 1 will still be 0, so it will shift to the right again. n → = 1 will make him shift another digit to the right, changing n from 110 (6) to 11 (3).

Now you can see that the last bit is 1, so n and 1 will be 1, as a result, the while loop will stop executing. The goal of the loop is to shift the number to the right until it finds the first enable bit (until the result is odd).

Answer 4

for example, if n was

 n= b11110000 

then

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

if the cycle continues, it should be

 n= b00001111 

Answer 5

Suppose it is 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 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 false (because n & 1 == 1 or 0000 0000 0000 0000 0000 0000 0000 0001 )

What does he do:

Basically, you loop n by 2 until n is an even number:

• n and 1 are a simple parity check,
• n → = 1 shifts the bits to the right, which simply divides by 2.

Answer 6

n and 1 is actually a bitwise AND operation. Here, bit chart n will be ANDED versus bit chart 1. The result will be compared to zero. If yes, then n shifts to the right 1 time. You can take one right shift as division by 2, etc.