Reverse Bits of a Number in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the result variable to zero.

DSA C++

unsigned int reverseBits(unsigned int n) {
    unsigned int result = [1];
    for (int i = 0; i < 32; i++) {
        // loop body
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A0

B1

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing result with n instead of 0.

Using -1 which sets all bits to 1.

We start with result = 0 because we will build the reversed bits from scratch.

2fill in blank

medium

Complete the code to extract the least significant bit of n.

DSA C++

unsigned int reverseBits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        unsigned int bit = n [1] 1;
        // process bit
        n >>= 1;
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A<<

B|

C^

D&

Attempts:

3 left

💡 Hint

Common Mistakes

Using OR or XOR instead of AND.

Using shift operators instead of bitwise AND.

Using bitwise AND with 1 extracts the least significant bit of n.

3fill in blank

hard

Fix the error in updating the result by shifting and adding the bit.

DSA C++

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

Drag options to blanks, or click blank then click option'

A+

B>>

C<<

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using right shift instead of left shift.

Using addition instead of bitwise OR.

We shift result left by 1 to make space for the new bit, then add it with OR.

4fill in blank

hard

Fill both blanks to complete the loop that reverses bits correctly.

DSA C++

unsigned int reverseBits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < [1]; i++) {
        unsigned int bit = n [2] 1;
        result = (result << 1) | bit;
        n >>= 1;
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A32

B16

C&

D|

Attempts:

3 left

💡 Hint

Common Mistakes

Looping 16 times instead of 32.

Using OR instead of AND to extract bits.

We loop 32 times for 32 bits and use bitwise AND to get the last bit.

5fill in blank

hard

Fill all three blanks to create a function that reverses bits of an unsigned int.

DSA C++

unsigned int reverseBits(unsigned int n) {
    unsigned int result = [1];
    for (int i = 0; i < [2]; i++) {
        unsigned int bit = n [3] 1;
        result = (result << 1) | bit;
        n >>= 1;
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A0

B32

C&

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting result with 1 instead of 0.

Looping fewer than 32 times.

Using | instead of & to extract bits.

Initialize result to 0, loop 32 times, and use & 1 to get the last bit.

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