Reverse Bits of a Number in DSA Go - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with number n

↓

Initialize result = 0

↓

Loop 32 times

↓

Shift result left by 1

↓

Extract last bit of n

↓

Add extracted bit to result

↓

Shift n right by 1

↓

Repeat loop

↓

Return result with bits reversed

We take each bit from the original number from right to left and add it to the result from left to right, effectively reversing the bits.

Execution Sample

DSA Go

func reverseBits(n uint32) uint32 {
    var result uint32 = 0
    for i := 0; i < 32; i++ {
        result <<= 1
        result |= n & 1
        n >>= 1
    }
    return result
}

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

Execution Table

Step	Operation	n (binary)	Extracted bit	result (binary)	Pointer Changes	Visual State
1	Initialize result=0	00000000000000000000000000001010	-	00000000000000000000000000000000	result=0, n=10	result=0, n=10 (binary 1010)
2	Shift result left by 1	00000000000000000000000000001010	-	00000000000000000000000000000000	result <<=1	result=0
3	Extract last bit of n	00000000000000000000000000001010	0	00000000000000000000000000000000	bit = n & 1 = 0	bit=0
4	Add bit to result	00000000000000000000000000001010	0	00000000000000000000000000000000	result |= bit	result=0
5	Shift n right by 1	00000000000000000000000000000101	-	00000000000000000000000000000000	n >>=1	n=5 (binary 101)
6	Shift result left by 1	00000000000000000000000000000101	-	00000000000000000000000000000000	result <<=1	result=0
7	Extract last bit of n	00000000000000000000000000000101	1	00000000000000000000000000000000	bit = 1	bit=1
8	Add bit to result	00000000000000000000000000000101	1	00000000000000000000000000000001	result |= 1	result=1
9	Shift n right by 1	00000000000000000000000000000010	-	00000000000000000000000000000001	n >>=1	n=2 (binary 10)
10	Shift result left by 1	00000000000000000000000000000010	-	00000000000000000000000000000010	result <<=1	result=2
11	Extract last bit of n	00000000000000000000000000000010	0	00000000000000000000000000000010	bit=0	bit=0
12	Add bit to result	00000000000000000000000000000010	0	00000000000000000000000000000010	result |= 0	result=2
13	Shift n right by 1	00000000000000000000000000000001	-	00000000000000000000000000000010	n >>=1	n=1 (binary 1)
14	Shift result left by 1	00000000000000000000000000000001	-	00000000000000000000000000000100	result <<=1	result=4
15	Extract last bit of n	00000000000000000000000000000001	1	00000000000000000000000000000100	bit=1	bit=1
16	Add bit to result	00000000000000000000000000000001	1	00000000000000000000000000000101	result |= 1	result=5
17	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000000101	n >>=1	n=0 (binary 0)
18	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000001010	result <<=1	result=10
19	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000000001010	bit=0	bit=0
20	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000000001010	result |= 0	result=10
21	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000001010	n >>=1	n=0
22	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000010100	result <<=1	result=20
23	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000000010100	bit=0	bit=0
24	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000000010100	result |= 0	result=20
25	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000010100	n >>=1	n=0
26	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000101000	result <<=1	result=40
27	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000000101000	bit=0	bit=0
28	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000000101000	result |= 0	result=40
29	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000101000	n >>=1	n=0
30	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000001010000	result <<=1	result=80
31	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000001010000	bit=0	bit=0
32	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000001010000	result |= 0	result=80
33	Loop ends	-	-	00000000000000000000000001010000	-	Final reversed bits = 80

💡 Loop completes 32 iterations, all bits processed and reversed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
n	00000000000000000000000000001010	00000000000000000000000000000101	00000000000000000000000000000010	00000000000000000000000000000001	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000
result	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000010	00000000000000000000000000000101	00000000000000000000000000001010	00000000000000000000000000010100	00000000000000000000000000101000	00000000000000000000000001010000	00000000000000000000000001010000

Key Moments - 3 Insights

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

Because shifting result left makes space for the new bit at the rightmost position, effectively building the reversed number from left to right as we extract bits from right to left (see execution_table steps 2 and 3).

Why do we use n & 1 to extract the last bit?

Using n & 1 masks all bits except the last one, giving us the rightmost bit of n at each step (see execution_table step 3).

What happens when n becomes zero before 32 iterations?

We continue shifting result and adding zeros because we must process all 32 bits to reverse the entire number (see execution_table steps 17 to 32).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the binary value of result?

A 00000000000000000000000000000001

B 00000000000000000000000000000010

C 00000000000000000000000000000000

D 00000000000000000000000000000101

💡 Hint

Check the 'result (binary)' column at step 8 in the execution_table.

At which step does n first become zero in the execution_table?

A Step 14

B Step 17

C Step 10

D Step 20

💡 Hint

Look at the 'n (binary)' column and find when it changes to all zeros.

If we did not shift result left before adding the bit, how would the final result change?

A The bits would be reversed correctly anyway.

B The result would be zero.

C The bits would not be reversed; result would accumulate bits incorrectly.

D The result would be the same as the input number.

💡 Hint

Refer to the key_moments explanation about why shifting result left is necessary.

Concept Snapshot

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

Full Transcript

This concept shows how to reverse the bits of a 32-bit unsigned integer. We start with the number n and a result initialized to zero. We loop 32 times, each time shifting the result left by one to make space for the next bit. We extract the last bit of n using n & 1 and add it to the result. Then we shift n right by one to process the next bit. After 32 iterations, the result contains the bits of n reversed. The execution table traces each step, showing how n and result change in binary. Key moments clarify why we shift result before adding bits and why we continue even if n becomes zero early. The visual quiz tests understanding of these steps. This method ensures all bits are reversed correctly.

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 0s to 1s and 1s to 0s

Solution

1. Step 1: Understand bit representation

   Numbers are stored as bits (0s and 1s) in a sequence from left (most significant) to right (least significant).

2. Step 2: Define reversing bits

   Reversing bits means taking the bit sequence and flipping it so the first bit becomes last, second becomes second last, and so on.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Reverse bits means flip their order, not flip values [OK]

Common Mistakes:

• Confusing reversing bits with bitwise NOT (flip 0s and 1s)
• Thinking reversing bits means adding or subtracting
• Mixing reversing bits with shifting bits

2. Which Go code snippet correctly reverses bits of a 8-bit unsigned integer n?

easy

A. var rev uint8 = 0
for i := 0; i < 8; i++ {
rev = rev >> 1
rev |= n & 1
n <<= 1
}

B. var rev uint8 = 0
for i := 0; i < 8; i++ {
rev |= (n & 1) << i
n >>= 1
}

C. var rev uint8 = 0
for i := 0; i < 8; i++ {
rev += n & 1
n <<= 1
}

D. var rev uint8 = 0
for i := 0; i < 8; i++ {
rev <<= 1
rev |= n & 1
n >>= 1
}

Solution

1. Step 1: Analyze bit reversal logic

   We shift rev left to make space, add the least significant bit of n, then shift n right to process next bit.

2. Step 2: Check code correctness

   var rev uint8 = 0 for i := 0; i < 8; i++ { rev <<= 1 rev |= n & 1 n >>= 1 } correctly shifts rev left, ORs with n's last bit, then shifts n right. Others either shift wrong direction or add bits incorrectly.

3. Final Answer:

   The code in A correctly reverses bits -> Option D

4. Quick Check:

   Shift rev left + add n's LSB + shift n right = correct [OK]

Hint: Shift rev left, add n's last bit, shift n right each loop [OK]

Common Mistakes:

• Shifting rev right instead of left
• Shifting n left instead of right
• Adding bits without shifting rev

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

func reverseBits(n uint8) uint8 {
  var rev uint8 = 0
  for i := 0; i < 8; i++ {
    rev <<= 1
    rev |= n & 1
    n >>= 1
  }
  return rev
}

fmt.Println(reverseBits(13))

Note: 13 in binary is 00001101.

medium

A. 176

B. 11

C. 101

D. 208

Solution

1. Step 1: Convert 13 to binary and reverse bits

   13 in 8 bits: 00001101. Reversing bits: 10110000.

2. Step 2: Convert reversed bits back to decimal

   10110000 binary = 128 + 32 + 16 = 176 decimal.

3. Final Answer:

   176 -> Option A

4. Quick Check:

   Reverse(00001101) = 10110000 = 176 [OK]

Hint: Reverse bits visually, then convert binary to decimal [OK]

Common Mistakes:

• Confusing bit order and reversing incorrectly
• Calculating decimal from wrong binary
• Ignoring leading zeros in 8-bit representation

4. Find the error in this Go function that tries to reverse bits of a 4-bit number:

func reverse4Bits(n uint8) uint8 {
  var rev uint8 = 0
  for i := 0; i < 4; i++ {
    rev |= (n & 1) << i
    n >>= 1
  }
  return rev
}

medium

A. The shift operator should be >> instead of <<

B. The loop should run 8 times for 4-bit numbers

C. The bits are not reversed; they are copied in the same order

D. Variable rev should be int, not uint8

Solution

1. Step 1: Understand the code logic

   The code shifts bits of n right, then sets rev bits by shifting left by i, which copies bits in same order.

2. Step 2: Identify why bits are not reversed

   Reversing bits requires shifting rev left each time and adding n's last bit, not shifting by i.

3. Final Answer:

   The bits are not reversed; they are copied in the same order -> Option C

4. Quick Check:

   Shifting rev by i copies bits, not reverses [OK]

Hint: Shift rev left each loop to reverse bits, not shift by i [OK]

Common Mistakes:

• Confusing bit copying with reversing
• Wrong loop count for bit size
• Incorrect variable types for bits

5. You want to reverse bits of a 16-bit unsigned integer and then check if the reversed number is a palindrome in binary (reads same forwards and backwards). Which approach is correct?

hard

A. Reverse bits using a loop, then compare reversed number with original

B. Reverse bits using a loop, then reverse again and compare with original

C. Check if original number equals reversed number without reversing bits

D. Shift bits left and right alternately without reversing

Solution

1. Step 1: Reverse bits of the number

   Use a loop to reverse all 16 bits to get reversed number.

2. Step 2: Check if reversed number is a palindrome

   To verify if reversed reads the same forwards and backwards, compute reverse(reversed) and check if it equals reversed. Since reverse(reversed) = original, this is equivalent to comparing reversed with original.

3. Final Answer:

   Reverse bits using a loop, then compare reversed number with original -> Option A

4. Quick Check:

   reversed == original iff reversed is palindrome [OK]

Hint: Reverse once, then compare reversed with original [OK]

Common Mistakes:

• Double reversing and comparing to original (always true, doesn't check palindrome)
• Trying to check equality without computing the reverse
• Using shifting without proper bit reversal