Reverse Bits of a Number in DSA Java - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with input number

↓

Initialize result = 0, count = 32

↓

Loop while count > 0

↓

Shift result left by 1

↓

Extract last bit of input

↓

Add extracted bit to result

↓

Shift input right by 1

↓

Decrement count

↓

Repeat loop

↓

Return result with bits reversed

We take each bit from the input number from right to left and build the reversed number by shifting and adding bits from left to right.

Execution Sample

DSA Java

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 adding bits one by one.

Execution Table

Step	Operation	Input (binary)	Extracted Bit	Result (binary)	Pointer Changes
1	Initialize result=0, n=00000000000000000000000000001011 (decimal 11)	00000000000000000000000000001011	-	00000000000000000000000000000000	result=0, n=11
2	Shift result left by 1	00000000000000000000000000001011	-	00000000000000000000000000000000	result=0
3	Extract last bit of n (1)	00000000000000000000000000001011	1	00000000000000000000000000000001	n=11
4	Add extracted bit to result	00000000000000000000000000001011	1	00000000000000000000000000000001	result=1
5	Shift n right by 1	00000000000000000000000000000101	-	00000000000000000000000000000001	n=5
6	Shift result left by 1	00000000000000000000000000000101	-	00000000000000000000000000000010	result=1
7	Extract last bit of n (1)	00000000000000000000000000000101	1	00000000000000000000000000000011	n=5
8	Add extracted bit to result	00000000000000000000000000000101	1	00000000000000000000000000000011	result=3
9	Shift n right by 1	00000000000000000000000000000010	-	00000000000000000000000000000011	n=2
10	Shift result left by 1	00000000000000000000000000000010	-	00000000000000000000000000000110	result=3
11	Extract last bit of n (0)	00000000000000000000000000000010	0	00000000000000000000000000000110	n=2
12	Add extracted bit to result	00000000000000000000000000000010	0	00000000000000000000000000000110	result=6
13	Shift n right by 1	00000000000000000000000000000001	-	00000000000000000000000000000110	n=1
14	Shift result left by 1	00000000000000000000000000000001	-	00000000000000000000000000001100	result=6
15	Extract last bit of n (1)	00000000000000000000000000000001	1	00000000000000000000000000001101	n=1
16	Add extracted bit to result	00000000000000000000000000000001	1	00000000000000000000000000001101	result=13
17	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000001101	n=0
18	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000011010	result=13
19	Extract last bit of n (0)	00000000000000000000000000000000	0	00000000000000000000000000011010	n=0
20	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000000011010	result=26
21	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000011010	n=0
22	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000110100	result=26
23	Extract last bit of n (0)	00000000000000000000000000000000	0	00000000000000000000000000110100	n=0
24	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000000110100	result=52
25	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000110100	n=0
26	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000001101000	result=52
27	Extract last bit of n (0)	00000000000000000000000000000000	0	00000000000000000000000001101000	n=0
28	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000001101000	result=104
29	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000001101000	n=0
30	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000011010000	result=104
31	Extract last bit of n (0)	00000000000000000000000000000000	0	00000000000000000000000011010000	n=0
32	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000011010000	result=208
33	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000011010000	n=0
34	Loop ends after 32 steps	-	-	00000000000000000000000011010000	Final result=208

💡 Loop completes after 32 iterations, all bits processed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
n	00000000000000000000000000001011 (11)	00000000000000000000000000000101 (5)	00000000000000000000000000000010 (2)	00000000000000000000000000000001 (1)	00000000000000000000000000000000 (0)	0	0	0	0	0
result	00000000000000000000000000000000 (0)	00000000000000000000000000000001 (1)	00000000000000000000000000000011 (3)	00000000000000000000000000000110 (6)	00000000000000000000000000001101 (13)	00000000000000000000000000011010 (26)	00000000000000000000000000110100 (52)	00000000000000000000000001101000 (104)	00000000000000000000000011010000 (208)	00000000000000000000000011010000 (208)

Key Moments - 3 Insights

Why do we shift the result left before adding the extracted bit?

Shifting result left makes room for the new bit on the right side. This is shown in execution_table rows 2 and 6 where result is shifted before adding the bit.

Why do we extract the last bit of n using (n & 1)?

The expression (n & 1) gets the rightmost bit of n. This is the bit we want to add to the reversed result, as seen in rows 3, 7, 11, etc.

Why do we shift n right after extracting the bit?

Shifting n right moves the next bit into the last position for extraction in the next loop. This is shown in rows 5, 9, 13, etc.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the extracted bit from n?

A 0

B 2

C 1

D Undefined

💡 Hint

Check the 'Extracted Bit' column at step 7 in execution_table

At which step does the input n become zero?

A Step 13

B Step 17

C Step 5

D Step 34

💡 Hint

Look at the 'Input (binary)' column in execution_table and find when n is all zeros

If we did not shift result left before adding the bit, what would happen?

A Bits would be added in wrong order, giving incorrect reversal

B Result would always be zero

C Bits would be reversed correctly

D Input n would change

💡 Hint

Refer to key_moments about why shifting result left is important before adding bits

Concept Snapshot

Reverse Bits of a Number:
- Initialize result=0
- Loop 32 times:
  - Shift result left by 1
  - Add last bit of input n to result
  - Shift input n right by 1
- Return result
This reverses the bits of a 32-bit integer by building the reversed number bit-by-bit.

Full Transcript

This visualization shows how to reverse bits of a 32-bit number. We start with the input number and an empty result. Each step shifts the result left to make space, extracts the last bit of the input, adds it to the result, then shifts the input right to process the next bit. After 32 steps, all bits are reversed in the result. The execution table tracks the binary states of input and result, showing how bits move. Key moments clarify why shifting and bit extraction happen in this order. The quiz tests understanding of bit extraction, input zeroing, and the importance of shifting result before adding bits.

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