LeetCode 190 Reverse Bits Solution In Java | Step By Step Explanation

Let me walk you through each of the bitwise operations involved, using a concrete example and representation for better understanding.

Example:

Suppose we have n = 13. In binary, this is represented as:

n = 00000000000000000000000000001101

Now, let's look at each operation step by step:

1. result <<= 1;

This is the left shift operation. It shifts all bits in the variable result to the left by 1 position. Initially, let's assume result = 0.

Initial result:

result = 00000000000000000000000000000000

After result <<= 1:

• All bits are shifted to the left by 1.
• A 0 is added to the least significant bit (rightmost bit).

After result <<= 1:

result = 00000000000000000000000000000000

Since result was 0, nothing visibly changes. But as this operation continues in future iterations, it will help accumulate the reversed bits.

2. result |= (n & 1);

This is a combination of bitwise AND (n & 1) and bitwise OR (result |=).

• n & 1 extracts the last bit of n (the least significant bit). It works by AND-ing n with 1, which masks all other bits except the last one.

For n = 13 (00000000000000000000000000001101): 

n & 1 = 00000000000000000000000000001101

         &

         00000000000000000000000000000001

       = 00000000000000000000000000000001

So, n & 1 = 1.

Then, we OR this with result. Since result = 0, it updates result:

result |= 1  (this sets the least significant bit of result to 1)

 Result after OR operation:

result = 00000000000000000000000000000001

3. n >>= 1;

This is the right shift operation. It shifts all bits in n to the right by 1 position, effectively removing the least significant bit. This prepares n for the next iteration.

Before right shift (n = 13):

n = 00000000000000000000000000001101

After n >>= 1:

n = 00000000000000000000000000000110

Now, the new value of n is 6, which will be processed in the next iteration.

Summary of Iteration:

Let's go through these steps for the first two iterations with n = 13 (00000000000000000000000000001101):

1. First Iteration:

• result <<= 1

result = 00000000000000000000000000000000

result |= (n & 1):

• n & 1 = 1
• result = 00000000000000000000000000000001

n >>= 1

n = 00000000000000000000000000000110

Second Iteration:

• result <<= 1
  

  result = 00000000000000000000000000000010

• result |= (n & 1):
  • n & 1 = 0
  • result = 00000000000000000000000000000010
• n >>= 1
• n = 00000000000000000000000000000011
  
  

  In the end, after 32 iterations, result will contain the reversed bits of the original n. For n = 13, its reversed bits are 11100000000000000000000000000000, which corresponds to 3758096384 in decimal.

  These operations allow the bits of n to be processed and reversed step by step.