Why Reverse Bits of a Number in DSA C++?

The Big Idea

What if flipping bits could be done in a blink, not by slow, error-prone manual work?

The Scenario

Imagine you have a number represented in binary, like a row of light switches turned on or off. You want to flip the order of these switches so the first becomes last and the last becomes first. Doing this by hand means checking each switch one by one and moving it to the new position.

The Problem

Manually flipping each bit is slow and easy to mess up, especially if the number has many bits. Counting positions and moving bits without mistakes is tricky and takes a lot of time.

The Solution

Using a simple algorithm, we can automatically reverse the bits by shifting and masking bits step-by-step. This method is fast, reliable, and works for any number size without confusion.

Before vs After

✗ Before

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

✓ After

unsigned int reverseBits(unsigned int number) {
  unsigned int reversed = 0;
  for (int i = 0; i < 32; i++) {
    reversed <<= 1;
    reversed |= (number & 1);
    number >>= 1;
  }
  return reversed;
}

What It Enables

This lets us quickly flip the order of bits in any number, which is useful in tasks like data encoding, graphics, and network communication.

Real Life Example

In computer graphics, reversing bits helps in generating patterns or textures by flipping pixel data efficiently.

Key Takeaways

Manual bit reversal is slow and error-prone.

Algorithmic bit reversal uses shifting and masking for speed and accuracy.

This technique is key in many computer science applications like encoding and graphics.

Practice

1. What does reversing the bits of a number mean in binary representation?

easy

A. Adding 1 to the binary number

B. Changing all 0s to 1s and 1s to 0s

C. Shifting bits to the left by one position

D. Flipping the order of bits from left to right

Solution

1. Step 1: Understand bit order

   Bits are arranged from left (most significant) to right (least significant). Reversing means swapping their order.

2. Step 2: Differentiate from other operations

   Flipping bits means changing 0 to 1 or 1 to 0, which is different from reversing order.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

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

Common Mistakes:

• Confusing reversing bits with flipping bits
• Thinking reversing means shifting bits
• Assuming reversing adds or subtracts value

2. Which of the following C++ code snippets correctly reverses the bits of an 8-bit unsigned integer n?

easy

A. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
```

B. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result |= (n & 1) << i;
n >>= 1;
}
return result;
}
```

C. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result <<= 1;
result |= ((n >> i) & 1);
}
return result;
}
```

D. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 7; i >= 0; i--) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
```

Solution

1. Step 1: Analyze the loop and bit operations

   ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result <<= 1; result |= (n & 1); n >>= 1; } return result; } ``` shifts result left, adds least significant bit of n, then shifts n right. This reverses bits correctly.

2. Step 2: Check other options for correctness

   ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result |= (n & 1) << i; n >>= 1; } return result; } ``` does not reverse bits, it copies bits in same order. ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result <<= 1; result |= ((n >> i) & 1); } return result; } ``` uses wrong bit extraction. ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 7; i >= 0; i--) { result <<= 1; result |= (n & 1); n >>= 1; } return result; } ``` has wrong loop condition causing infinite loop if i-- is missing.

3. Final Answer:

   Option A code correctly reverses bits -> Option A

4. Quick Check:

   Shift result left + add LSB of n each step [OK]

Hint: Shift result left, add LSB of n, shift n right [OK]

Common Mistakes:

• Using wrong loop conditions causing infinite loops
• Not shifting result before adding bits
• Extracting bits incorrectly with wrong shifts

3. What is the output of the following C++ code snippet?

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

int main() {
  unsigned char n = 13; // binary 00001101
  unsigned char reversed = reverseBits(n);
  std::cout << (int)reversed << std::endl;
  return 0;
}

medium

A. 101

B. 176

C. 11

D. 208

Solution

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

   13 in 8-bit binary is 00001101. Reversing bits gives 10110000.

2. Step 2: Convert reversed binary to decimal

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

3. Final Answer:

   176 -> Option B

4. Quick Check:

   00001101 reversed = 10110000 = 176 [OK]

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

Common Mistakes:

• Confusing bit reversal with bit flipping
• Not casting unsigned char to int for output
• Misreading binary to decimal conversion

4. Identify the bug in this C++ function that attempts to reverse bits of a 4-bit number:

unsigned char reverseBits4(unsigned char n) {
  unsigned char result = 0;
  for (int i = 0; i <= 4; i++) {
    result <<= 1;
    result |= (n & 1);
    n >>= 1;
  }
  return result;
}

medium

A. Loop runs one extra time causing incorrect result

B. Bitwise OR operator is used incorrectly

C. Result is not shifted before OR operation

D. Function does not return a value

Solution

1. Step 1: Check loop range

   The loop runs from i=0 to i=4 inclusive, so 5 iterations instead of 4.

2. Step 2: Understand effect of extra iteration

   Extra iteration shifts result and adds an extra bit, corrupting the reversed bits.

3. Final Answer:

   Loop runs one extra time causing incorrect result -> Option A

4. Quick Check:

   Loop should run 4 times, not 5 [OK]

Hint: Use < instead of <= for loop count [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Forgetting to shift result before OR
• Ignoring return statement correctness

5. Given a 16-bit unsigned integer, how would you efficiently reverse its bits using a divide-and-conquer approach in C++?

hard

A. Use recursion to reverse bits by dividing number by 2 repeatedly

B. Use a loop to reverse bits one by one shifting result left each time

C. Swap bits in pairs, then nibbles, then bytes, then half-words using masks and shifts

D. Convert number to string, reverse string, then convert back to integer

Solution

1. Step 1: Understand divide-and-conquer bit reversal

   Divide bits into pairs, swap them; then groups of 4 bits (nibbles), swap; then bytes, then half-words.

2. Step 2: Use masks and shifts for efficient swapping

   Use bit masks to isolate groups and shift them to swap positions without looping over each bit.

3. Final Answer:

   Swap bits in pairs, then nibbles, then bytes, then half-words using masks and shifts -> Option C

4. Quick Check:

   Divide-and-conquer uses masks and shifts [OK]

Hint: Swap bits in groups using masks and shifts [OK]

Common Mistakes:

• Using slow bit-by-bit loops for large bit sizes
• Trying string conversion which is inefficient
• Misunderstanding recursion for bit reversal