Reverse Bits of a Number in DSA Go - Deep Dive

Overview - Reverse Bits of a Number

What is it?

Reversing bits of a number means flipping the order of its binary digits. For example, if a number's bits are 1011, reversing them gives 1101. This operation changes the number's value by rearranging its bits from right to left. It is a common task in low-level programming and computer science.

Why it matters

Reversing bits is important in areas like cryptography, graphics, and network protocols where bit-level manipulation is needed. Without this concept, programmers would struggle to efficiently transform data at the binary level, leading to slower or more complex code. It helps optimize performance and solve problems that depend on bit patterns.

Where it fits

Before learning this, you should understand binary numbers and bitwise operations like AND, OR, and shifts. After mastering bit reversal, you can explore advanced bit manipulation techniques and algorithms that rely on bit patterns, such as fast hashing or compression.

Mental Model

Core Idea

Reversing bits means reading a number's binary digits from right to left and writing them back left to right, flipping their order.

Think of it like...

Imagine a row of light switches turned on or off in a certain order. Reversing bits is like walking along the row from the end to the start and flipping the order of the switches exactly as you see them.

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

Build-Up - 6 Steps

1

Foundation

Understanding Binary Representation

Concept: Learn how numbers are stored as sequences of bits (0s and 1s).

Every number in a computer is stored in binary form. For example, the decimal number 13 is 1101 in binary. Each bit represents a power of two, starting from the right (least significant bit). Understanding this helps us manipulate numbers at the bit level.

Result

You can convert decimal numbers to binary and recognize each bit's position.

Understanding binary is essential because reversing bits only makes sense when you know what each bit represents.

2

Foundation

Basics of Bitwise Operations

Concept: Introduce bitwise operators like AND, OR, and shifts to manipulate bits.

Bitwise AND (&) compares bits and returns 1 only if both bits are 1. Bitwise OR (|) returns 1 if at least one bit is 1. Left shift (<<) moves bits to the left, adding zeros on the right. Right shift (>>) moves bits to the right, discarding bits on the right.

Result

You can isolate, set, or move bits within a number.

Knowing bitwise operations is crucial because reversing bits involves shifting and checking individual bits.

3

Intermediate

Step-by-Step Bit Reversal Logic

🤔Before reading on: do you think reversing bits means swapping bits pairwise or reading bits in reverse order? Commit to your answer.

Concept: Reversing bits means reading each bit from right to left and placing it from left to right in a new number.

To reverse bits, start with a result of 0. For each bit in the original number, shift the result left by 1 to make space, then add the current bit from the original number. Repeat until all bits are processed.

Result

You get a new number whose bits are the reverse of the original.

Understanding the process as building a new number bit by bit clarifies why shifting and adding bits works.

4

Intermediate

Implementing Bit Reversal in Go

🤔Before reading on: do you think a loop or recursion is better for reversing bits? Commit to your answer.

Concept: Use a loop to iterate over each bit, shifting and adding bits to reverse the number.

func reverseBits(num uint32) uint32 { var result uint32 = 0 for i := 0; i < 32; i++ { result <<= 1 result |= num & 1 num >>= 1 } return result } // Example: reverseBits(13) returns 2952790016

Result

The function returns the reversed bit number correctly for 32-bit unsigned integers.

Using a loop with shifts and bitwise OR efficiently reverses bits without extra memory.

5

Advanced

Optimizing Bit Reversal with Lookup Tables

🤔Before reading on: do you think reversing bits byte-by-byte is faster than bit-by-bit? Commit to your answer.

Concept: Use a precomputed table to reverse bits of smaller parts (like bytes) and combine results for speed.

Create a 256-entry table where each entry is the reversed bits of a byte. To reverse a 32-bit number, split it into 4 bytes, reverse each using the table, then combine them in reverse order. Example: var lookup [256]uint8 // Initialize lookup with reversed bytes func reverseBits(num uint32) uint32 { return uint32(lookup[num&0xff]) << 24 | uint32(lookup[(num>>8)&0xff]) << 16 | uint32(lookup[(num>>16)&0xff]) << 8 | uint32(lookup[(num>>24)&0xff]) }

Result

Bit reversal runs faster by avoiding bit-by-bit processing.

Precomputing reversals trades memory for speed, a common optimization in performance-critical code.

6

Expert

Bit Reversal in Hardware and Parallelism

🤔Before reading on: do you think bit reversal can be done faster using parallel bit swaps? Commit to your answer.

Concept: Hardware and advanced algorithms use parallel bit swapping to reverse bits in fewer steps.

Bit reversal can be done by swapping pairs of bits, then groups of 4 bits, then 8 bits, and so on, using masks and shifts. This reduces the number of operations by handling multiple bits at once. Example snippet: num = ((num >> 1) & 0x55555555) | ((num & 0x55555555) << 1) num = ((num >> 2) & 0x33333333) | ((num & 0x33333333) << 2) num = ((num >> 4) & 0x0F0F0F0F) | ((num & 0x0F0F0F0F) << 4) num = ((num >> 8) & 0x00FF00FF) | ((num & 0x00FF00FF) << 8) num = ((num >> 16) & 0x0000FFFF) | ((num & 0x0000FFFF) << 16)

Result

Bit reversal completes in a fixed number of operations regardless of bit count.

Parallel bit swapping exploits bit patterns and masks to optimize reversal beyond simple loops.

Under the Hood

Reversing bits works by extracting each bit from the original number starting from the least significant bit, then inserting it into the result starting from the most significant bit. This is done using bitwise AND to isolate bits, shifts to move bits into position, and bitwise OR to set bits in the result. The process iterates over all bits, effectively mirroring the bit pattern.

Why designed this way?

This approach was chosen because bitwise operations are very fast and map directly to CPU instructions. Using shifts and masks avoids complex arithmetic and allows bit reversal to be done efficiently in software or hardware. Alternatives like string conversion are slower and less practical for low-level tasks.

Original number bits:  [b31 b30 ... b2 b1 b0]
Process:              ↓ Extract bit b0
                      ↓ Shift result left
                      ↓ Insert b0 at left
Repeat for all bits
Result bits:          [b0 b1 b2 ... b30 b31]

Myth Busters - 4 Common Misconceptions

Quick: Does reversing bits change the number's value in a predictable way? Commit yes or no.

Common Belief: Reversing bits just flips the number's bits but keeps the value similar or related.

Reality: Reversing bits usually produces a completely different number with no simple relation to the original value.

Why it matters: Assuming a predictable value change can cause bugs in algorithms relying on bit patterns, like checksums or encoding.

Quick: Is reversing bits the same as reversing the decimal digits? Commit yes or no.

Common Belief: Reversing bits is like reversing the decimal digits of a number.

Reality: Bits and decimal digits are different representations; reversing bits changes the binary pattern, not the decimal digit order.

Why it matters: Confusing these leads to wrong implementations and misunderstandings of bit-level operations.

Quick: Can you reverse bits by converting to string and reversing characters? Commit yes or no.

Common Belief: Converting the number to a binary string and reversing it is the best way to reverse bits.

Reality: While possible, string conversion is inefficient and slow compared to bitwise operations.

Why it matters: Using string methods in performance-critical code causes unnecessary overhead and slows down programs.

Quick: Does reversing bits always require processing all bits one by one? Commit yes or no.

Common Belief: You must process each bit individually to reverse bits.

Reality: Advanced methods use parallel bit swaps and masks to reverse bits in fewer steps.

Why it matters: Not knowing this limits optimization opportunities in high-performance or hardware-level code.

Expert Zone

1

Bit reversal can be combined with other bitwise tricks like counting set bits or parity checks for complex algorithms.

2

Endianness (byte order) affects how reversed bits are interpreted in multi-byte data, requiring careful handling.

3

Lookup tables for bit reversal must be carefully initialized and can be cached for repeated use to save time.

When NOT to use

Avoid bit reversal when working with floating-point numbers or data where bit order does not affect meaning. Instead, use standard data transformations or encoding methods. Also, for very large bit widths, specialized hardware or parallel algorithms may be better.

Production Patterns

Bit reversal is used in graphics shaders for pixel manipulation, in cryptographic algorithms for bit scrambling, and in network protocols for endian conversion. Optimized bit reversal functions are often part of standard libraries or hardware instructions.

Connections

Endianness

Bit reversal relates to byte order reversal in endianness, both involve reordering bits or bytes.

Understanding bit reversal helps grasp how data is stored and interpreted differently on various systems.

Signal Processing

Bit reversal is used in algorithms like the Fast Fourier Transform (FFT) to reorder data efficiently.

Knowing bit reversal clarifies how FFT rearranges input data for faster computation.

Mirror Symmetry in Physics

Bit reversal mirrors bit patterns like mirror symmetry flips physical objects.

Recognizing this symmetry helps understand transformations that invert structures in different fields.

Common Pitfalls

#1 Ignoring the fixed bit width and reversing only the bits present in the number's binary form.

Wrong approach:

func reverseBits(num uint32) uint32 {
var result uint32 = 0
for num > 0 {
result <<= 1
result |= num & 1
num >>= 1
}
return result
}

Correct approach:

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

Root cause:

Not processing all bits leads to incorrect reversal because leading zeros are ignored.

#2 Using signed integers and shifting right without unsigned shift, causing sign extension.

Wrong approach:

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

Correct approach:

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

Root cause:

Signed right shift replicates the sign bit, corrupting the bit pattern.

#3 Reversing bits by converting to string and back, causing performance issues.

Wrong approach:

func reverseBits(num uint32) uint32 {
s := fmt.Sprintf("%032b", num)
reversed := ""
for i := len(s) - 1; i >= 0; i-- {
reversed += string(s[i])
}
val, _ := strconv.ParseUint(reversed, 2, 32)
return uint32(val)
}

Correct approach:

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

Root cause:

Using string conversion is inefficient and unnecessary for bit manipulation.

Key Takeaways

Reversing bits flips the order of binary digits, changing the number's bit pattern completely.

Bitwise operations like shifts and masks are the fastest and most direct way to reverse bits.

Optimizations like lookup tables and parallel bit swaps improve performance for large or repeated operations.

Understanding bit reversal is essential for low-level programming, cryptography, and algorithms like FFT.

Common mistakes include ignoring fixed bit width, using signed shifts, and relying on slow string conversions.

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