Reverse Bits of a Number in DSA Go

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 in the new row.

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

Dry Run Walkthrough

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

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

Step 1: Extract least significant bit (rightmost) 1 and add it to result

input bits: 00001101 -> extracted bit: 1 -> result bits: 00000001

Why: We start building reversed bits from the rightmost bit

Step 2: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000110 -> result bits: 00000010

Why: Prepare to extract next bit and make space in result

Step 3: Extract next bit 0 and add to result

input bits: 00000110 -> extracted bit: 0 -> result bits: 00000010

Why: Add next bit in reversed order

Step 4: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000011 -> result bits: 00000100

Why: Move to next bit

Step 5: Extract next bit 1 and add to result

input bits: 00000011 -> extracted bit: 1 -> result bits: 00000101

Why: Add next bit in reversed order

Step 6: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000001 -> result bits: 00001010

Why: Move to next bit

Step 7: Extract next bit 1 and add to result

input bits: 00000001 -> extracted bit: 1 -> result bits: 00001011

Why: Add next bit in reversed order

Step 8: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000000 -> result bits: 00010110

Why: Move to next bit

Step 9: Extract next bit 0 and add to result

input bits: 00000000 -> extracted bit: 0 -> result bits: 00010110

Why: Add next bit in reversed order

Step 10: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000000 -> result bits: 00101100

Why: Move to next bit

Step 11: Extract next bit 0 and add to result

input bits: 00000000 -> extracted bit: 0 -> result bits: 00101100

Why: Add next bit in reversed order

Step 12: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000000 -> result bits: 01011000

Why: Move to next bit

Step 13: Extract next bit 0 and add to result

input bits: 00000000 -> extracted bit: 0 -> result bits: 01011000

Why: Add next bit in reversed order

Step 14: Shift input right by 1 bit, shift result left by 1 bit

input bits: 00000000 -> result bits: 10110000

Why: Move to next bit

Result:

Reversed bits: 10110000 -> decimal 176

Annotated Code

DSA Go

package main

import "fmt"

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

func main() {
	input := uint8(13) // 00001101
	output := reverseBits(input)
	fmt.Printf("Input: %08b\n", input)
	fmt.Printf("Reversed: %08b\n", output)
	fmt.Printf("Reversed decimal: %d\n", output)
}

bit := num & 1

Extract least significant bit from input

result = (result << 1) | bit

Shift result left and add extracted bit to build reversed bits

num >>= 1

Shift input right to process next bit

Output

Input: 00001101

Reversed: 10110000

Reversed decimal: 176

Complexity Analysis

Time: O(1) because the number of bits is fixed (8 bits) and we always do 8 steps

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: This approach is optimal for fixed bit size; naive methods might convert to string and reverse, which is slower and uses more space

Edge Cases

input is 0 (all bits zero)

Output is also 0, as reversing zeros stays zero

DSA Go

for i := 0; i < 8; i++ {

input is 255 (all bits one)

Output is also 255, reversing all ones stays all ones

DSA Go

for i := 0; i < 8; i++ {

input has alternating bits like 170 (10101010)

Output is reversed pattern 85 (01010101)

DSA Go

result = (result << 1) | bit

When to Use This Pattern

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

Common Mistakes

Mistake: Shifting the input left instead of right, causing infinite loop or wrong bits
Fix: Shift input right (num >>= 1) to process bits from right to left

Mistake: Appending bits to result without shifting result left first, causing bits to overwrite
Fix: Always shift result left by 1 before adding new bit

Summary

Reverses the bits of an 8-bit number by extracting bits from right to left and building a new number from left to right.

Use when you need to flip the bit order of a fixed-size number, such as in low-level data processing or encoding.

The key insight is to extract bits one by one from the input's right side and add them to the result's left side by shifting.

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