Reverse Bits of a Number in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean to reverse the bits of a number?

Reversing the bits of a number means flipping the order of its binary digits from left to right. For example, if the binary is 1011, reversing it gives 1101.

beginner

How many bits are typically considered when reversing bits of an integer?

Usually, 32 bits are considered for a standard integer in many systems. This means reversing all 32 bits, including leading zeros.

intermediate

What is the first step in reversing bits of a number using bitwise operations?

The first step is to extract the least significant bit (rightmost bit) using bitwise AND with 1, then shift the reversed number to the left to build the reversed number.

intermediate

Why do we shift the reversed number to the left during the bit reversal process?

We shift the reversed number left to make space for the next bit from the original number, effectively building the reversed bit sequence from right to left.

intermediate

What is the time complexity of reversing bits of a 32-bit number?

The time complexity is O(1) because the number of bits (32) is fixed and does not grow with input size. The process always takes the same number of steps.

What operation is used to get the rightmost bit of a number?

A Bitwise AND with 1

B Bitwise OR with 1

C Left shift by 1

D Right shift by 1

Bitwise AND with 1 extracts the least significant bit (rightmost bit) of a number.

When reversing bits, why do we shift the original number to the right?

A To add zeros at the left

B To remove the bit we already processed

C To reverse the bits automatically

D To double the number

Shifting right removes the least significant bit after processing it, preparing for the next bit extraction.

How many bits are reversed in a standard 32-bit integer?

A 32

B 8

C 16

D 64

A standard integer has 32 bits, so all 32 bits are reversed.

What is the result of reversing bits of the binary number 00000000000000000000000000001010 (decimal 10)?

A 01010000000000000000000000000000

B 10100000000000000000000000000000

C 01010000000000000000000000000001

D 01010000000000000000000000000000 (decimal 1342177280)

Reversing bits of 10 (binary 1010) results in 0101 followed by zeros, which is decimal 1342177280.

What is the time complexity of reversing bits of a fixed-size integer?

A O(n), where n is the number of bits

B O(log n)

C O(1)

D O(n^2)

Since the number of bits is fixed (e.g., 32), the operation takes constant time O(1).

Explain step-by-step how to reverse the bits of a 32-bit number using bitwise operations.

Think about how to build the reversed number bit by bit.

Why is reversing bits useful in programming or computer science?

Consider practical applications where bit order matters.

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