Reverse Bits of a Number in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of reversing bits for 8-bit number

What is the output of the following C++ code that reverses the bits of an 8-bit unsigned integer 13?

DSA C++

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;
}

#include <iostream>
int main() {
    unsigned char x = 13; // binary 00001101
    unsigned char y = reverseBits(x);
    std::cout << (int)y << std::endl;
    return 0;
}

A 176

B 212

C 134

D 104

💡 Hint

Think about how bits shift and how the least significant bit moves to the most significant position.

The binary of 13 is 00001101. Reversing bits gives 10110000 which is 176 in decimal.

❓ Predict Output

intermediate

Output of reversing bits for 16-bit number

What is the output of reversing bits of the 16-bit unsigned integer 4660 using the given function?

DSA C++

unsigned short reverseBits16(unsigned short n) {
    unsigned short result = 0;
    for (int i = 0; i < 16; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

#include <iostream>
int main() {
    unsigned short x = 4660; // binary 0001001000110100
    unsigned short y = reverseBits16(x);
    std::cout << y << std::endl;
    return 0;
}

A 13312

B 11336

C 17476

D 13330

💡 Hint

Convert 4660 to binary, reverse bits, then convert back to decimal.

4660 in binary is 0001001000110100. Reversing bits gives 0010110001001000 which is 11336 decimal.

🔧 Debug

advanced

Identify the error in bit reversal code

What error does the following C++ code produce when trying to reverse bits of an 8-bit number?

DSA C++

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;
}

A Runs but returns incorrect result due to off-by-one loop

B Runtime error due to shifting beyond bit size

C Compilation error due to invalid syntax

D Runs correctly and returns reversed bits

💡 Hint

Check the loop condition carefully for how many times it runs.

The loop runs 9 times (i from 0 to 8 inclusive) instead of 8 times, causing an extra shift and wrong result.

❓ Predict Output

advanced

Output of reversing bits for 32-bit number

What is the output of reversing bits of the 32-bit unsigned integer 43261596 using the given function?

DSA C++

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

#include <iostream>
int main() {
    unsigned int x = 43261596; // binary 00000010100101000001111010011100
    unsigned int y = reverseBits32(x);
    std::cout << y << std::endl;
    return 0;
}

A 964176195

B 964176193

C 964176194

D 964176192

💡 Hint

Reverse the bits of the 32-bit number carefully and convert to decimal.

The reversed bits of 43261596 are 00111001011110000010100101000000 which equals 964176192 decimal.

🧠 Conceptual

expert

Number of set bits after reversing

If you reverse the bits of a 64-bit unsigned integer, what can you say about the number of set bits (bits with value 1) in the reversed number compared to the original?

A The number of set bits halves

B The number of set bits doubles

C The number of set bits remains the same

D The number of set bits becomes zero

💡 Hint

Reversing bits only changes their order, not their count.

Reversing bits only changes their positions, so the count of set bits remains unchanged.

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