Reverse Bits of a Number in DSA Java - Time & Space Complexity

Time Complexity: Reverse Bits of a Number

O(1)

Understanding Time Complexity

We want to understand how the time to reverse bits in a number changes as the number size changes.

Specifically, how many steps does it take to flip all bits from right to left?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

This code reverses the bits of a 32-bit integer by shifting and masking each bit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs 32 times, once for each bit.
• How many times: Exactly 32 times, fixed for 32-bit integers.

How Execution Grows With Input

Since the loop runs a fixed 32 times regardless of input value, the steps stay the same.

Input Size (n)	Approx. Operations
10 (binary 1010)	32 steps
100 (binary 1100100)	32 steps
1000 (binary 1111101000)	32 steps

Pattern observation: The number of steps does not grow with input size because the bit length is fixed.

Final Time Complexity

Time Complexity: O(1)

This means the time to reverse bits is constant and does not increase with the input number.

Common Mistake

[X] Wrong: "The time depends on the value of the number or its size."

[OK] Correct: The code always processes 32 bits, so time is fixed regardless of the number's value.

Interview Connect

Understanding fixed-time bit operations helps you handle low-level data tasks confidently in interviews and real projects.

Self-Check

"What if we changed the code to reverse bits of a 64-bit number? How would the time complexity change?"

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