Reverse Bits of a Number in DSA Java

Mental Model

Flip the order of bits in a number so the last bit becomes first and the first becomes last.

Analogy: Imagine a row of light switches turned on or off. Reversing bits is like walking to the end of the row and flipping the switches in reverse order, so the last switch's state becomes the first.

Original bits: 1 0 1 1 0 0 1 0
Reversed bits: 0 1 0 0 1 1 0 1

Dry Run Walkthrough

Input: number: 13 (binary 00001101, 8 bits for simplicity)

Goal: Reverse the bits of 13 to get 176 (binary 10110000)

Step 1: Extract rightmost bit (1) and add it to result shifted left

result = 00000001 (1), number = 00000110 (6)

Why: We start building reversed bits from right to left

Step 2: Extract next bit (0) and shift result left, add bit

result = 00000010 (2), number = 00000011 (3)

Why: Shift result to make room for next bit from number

Step 3: Extract next bit (1) and add to result

result = 00000101 (5), number = 00000001 (1)

Why: Add next bit in reversed order

Step 4: Extract next bit (1) and add to result

result = 00001011 (11), number = 00000000 (0)

Why: Continue until all bits processed

Step 5: Shift result left for remaining bits (4 more zeros)

result = 10110000 (176), number = 00000000 (0)

Why: Fill remaining bits with zeros as number bits exhausted

Result:

Reversed bits: 10110000 (decimal 176)

Annotated Code

DSA Java

public class ReverseBits {
    // Reverse bits of a 32-bit integer
    public static int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result <<= 1; // shift result left to make room
            result |= (n & 1); // add rightmost bit of n to result
            n >>>= 1; // shift n right logically to process next bit
        }
        return result;
    }

    public static void main(String[] args) {
        int input = 13; // binary 00000000000000000000000000001101
        int reversed = reverseBits(input);
        System.out.println(reversed); // expected 2952790016
    }
}

result <<= 1; // shift result left to make room

Shift reversed bits left to add next bit

result |= (n & 1); // add rightmost bit of n to result

Add current rightmost bit of n to reversed result

n >>>= 1; // shift n right logically to process next bit

Move to next bit of n by shifting right logically (unsigned shift)

Output

2952790016

Complexity Analysis

Time: O(1) because the number of bits (32) is fixed and loop runs constant times

Space: O(1) as only a few variables are used regardless of input size

vs Alternative: This approach is efficient and simple compared to converting to string and reversing, which uses extra space and more operations

Edge Cases

input is 0

result remains 0 after reversing bits

DSA Java

for (int i = 0; i < 32; i++) { ... }

input is all ones (e.g., -1 in 32-bit)

result remains all ones (same number) after reversing

DSA Java

for (int i = 0; i < 32; i++) { ... }

input has only one bit set (e.g., 1 or 16)

result has that bit reversed to the opposite end

DSA Java

result |= (n & 1);

When to Use This Pattern

When you need to reverse the order of bits in a number, use bitwise shifting and masking to build the reversed number bit by bit.

Common Mistakes

Mistake: Not shifting the result before adding the new bit, causing bits to overwrite
Fix: Always shift the result left before OR-ing the new bit

Mistake: Shifting the input number left instead of right, causing infinite loop or wrong bits
Fix: Shift the input number right to process bits from right to left

Summary

Reverses the bits of a 32-bit integer by shifting and masking.

Use when you need the mirror image of bits in a number for algorithms or encoding.

The key is to build the reversed number bit by bit by shifting result left and adding the rightmost bit of input.

Practice

1. What does reversing the bits of a number mean in simple terms?

easy

A. Shifting bits to the left by one position

B. Flipping the order of bits from left to right

C. Adding 1 to the number

D. Changing all bits from 0 to 1

Solution

1. Step 1: Understand bit order

   Bits are the 0s and 1s that make up a number. Reversing means flipping their order.

2. Step 2: Explain reversing bits

   If the bits are 1010, reversing them gives 0101, flipping left to right.

3. Final Answer:

   Flipping the order of bits from left to right -> Option B

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Think of bits like beads on a string flipped end to end [OK]

Common Mistakes:

• Confusing reversing bits with flipping bits (0 to 1)
• Thinking reversing means adding or subtracting
• Mixing bit shifting with bit reversing

2. Which Java syntax correctly reverses bits of an integer n using a loop?

easy

A. for (int i = 0; i < 32; i++) { result <<= 1; result |= (n & 1); n >>= 1; }

B. for (int i = 0; i < 32; i++) { result |= (n & 1) << i; n >>= 1; }

C. for (int i = 0; i < 32; i++) { result += (n & 1) << i; n <<= 1; }

D. for (int i = 0; i < 32; i++) { result <<= 1; result |= (n >> i) & 1; }

Solution

1. Step 1: Analyze bit extraction and shifting

   for (int i = 0; i < 32; i++) { result <<= 1; result |= (n & 1); n >>= 1; } extracts the least significant bit (n & 1), shifts result left, then adds the bit, and shifts n right.

2. Step 2: Check correctness of loop operations

   for (int i = 0; i < 32; i++) { result <<= 1; result |= (n & 1); n >>= 1; } correctly reverses bits by building result from left to right while moving through n's bits right to left.

3. Final Answer:

   for (int i = 0; i < 32; i++) { result <<= 1; result |= (n & 1); n >>= 1; } -> Option A

4. Quick Check:

   Shift result left, add bit from n, shift n right [OK]

Hint: Shift result left before adding extracted bit [OK]

Common Mistakes:

• Shifting n left instead of right
• Adding bits without shifting result
• Using incorrect bit extraction

3. What is the output of this Java code snippet?

int n = 13; // binary 00000000000000000000000000001101
int result = 0;
for (int i = 0; i < 4; i++) {
  result <<= 1;
  result |= (n & 1);
  n >>= 1;
}
System.out.println(result);

medium

A. 11

B. 13

C. 7

D. 14

Solution

1. Step 1: Trace each loop iteration

   Initial n=13 (binary 1101). Loop runs 4 times:
   i=0: result=0<<1=0; result|=1 (n&1=1); result=1; n=6
   i=1: result=1<<1=2; result|=0 (6&1=0); result=2; n=3
   i=2: result=2<<1=4; result|=1 (3&1=1); result=5; n=1
   i=3: result=5<<1=10; result|=1 (1&1=1); result=11; n=0

2. Step 2: Convert final result to decimal

   Result is 11 decimal after reversing 4 bits of 13.

3. Final Answer:

   11 -> Option A

4. Quick Check:

   Reversed 1101 bits = 1011 = 11 decimal [OK]

Hint: Reverse bits step-by-step, track result and n carefully [OK]

Common Mistakes:

• Not limiting loop to 4 bits
• Mixing bit order in result
• Confusing decimal and binary values

4. Find the error in this Java code that tries to reverse bits of a 8-bit number n:

int result = 0;
for (int i = 0; i <= 8; i++) {
  result <<= 1;
  result |= (n & 1);
  n >>= 1;
}

medium

A. Result should be shifted right, not left

B. Bitwise OR operator is used incorrectly

C. Loop runs one extra time causing wrong result

D. Variable n should not be shifted inside the loop

Solution

1. Step 1: Check loop range for 8 bits

   The loop runs from i=0 to i=8 inclusive, which is 9 iterations, but 8 bits need only 8 iterations.

2. Step 2: Understand effect of extra iteration

   Extra iteration shifts result one more time and adds an extra bit, causing incorrect reversed value.

3. Final Answer:

   Loop runs one extra time causing wrong result -> Option C

4. Quick Check:

   Loop should run 8 times, not 9 [OK]

Hint: Use < 8, not <= 8 for 8-bit loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Shifting result right instead of left
• Not shifting n inside loop

5. Given a 16-bit unsigned integer, how would you reverse its bits and return the result in Java? Which approach is best?

hard

A. Shift n left 16 times and OR with result

B. Convert number to binary string, reverse string, parse back to int

C. Use recursion to reverse bits one by one without loops

D. Use a loop shifting result left and extracting bits from n right, running 16 times

Solution

1. Step 1: Consider efficiency and correctness

   Looping 16 times, shifting result left and extracting bits from n right is efficient and direct for 16-bit reversal.

2. Step 2: Evaluate other options

   Converting to string is slower and error-prone; recursion adds overhead; shifting n left 16 times loses bits.

3. Final Answer:

   Use a loop shifting result left and extracting bits from n right, running 16 times -> Option D

4. Quick Check:

   Loop + bit shifts = best for fixed bit reversal [OK]

Hint: Loop 16 times, shift result left, add n's right bit [OK]

Common Mistakes:

• Using string conversion for bit operations
• Recursion without base case or efficiency
• Shifting n left losing original bits