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 reversing the bits of the 8-bit number 13 (00001101 in binary)?

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 <stdio.h>

int main() {
    unsigned char num = 13;
    unsigned char reversed = reverseBits(num);
    printf("%u\n", reversed);
    return 0;
}

A 104

B 176

C 134

D 212

💡 Hint

Think about how bits move from right to left when reversed.

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 the bits of the 16-bit number 4660 (0001001000110100 in binary)?

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 <stdio.h>

int main() {
    unsigned short num = 4660;
    unsigned short reversed = reverseBits16(num);
    printf("%u\n", reversed);
    return 0;
}

A 11336

B 13320

C 13312

D 13330

💡 Hint

Reverse the bits carefully from right to left for all 16 bits.

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

🔧 Debug

advanced

Identify the error in bit reversal code

What error does the following code produce when reversing 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 Compilation error due to loop condition

B Runs correctly and returns reversed bits

C Runs but returns incorrect result due to extra iteration

D Runtime error due to shifting beyond bit size

💡 Hint

Check the loop boundary condition carefully.

The loop runs 9 times (i <= 8), but should run 8 times (i < 8). The extra iteration shifts bits incorrectly causing wrong output.

❓ Predict Output

advanced

Output of reversing bits for 32-bit number

What is the output of reversing the bits of the 32-bit number 43261596 (00000010100101000001111010011100 in binary)?

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 <stdio.h>

int main() {
    unsigned int num = 43261596;
    unsigned int reversed = reverseBits32(num);
    printf("%u\n", reversed);
    return 0;
}

A 964176192

B 964176193

C 964176194

D 964176195

💡 Hint

Reverse all 32 bits carefully.

43261596 binary reversed is 00111001011110000010100101000000 which is 964176192 decimal.

🧠 Conceptual

expert

Why is bit reversal useful in algorithms?

Which of the following is the main reason bit reversal is used in algorithms like Fast Fourier Transform (FFT)?

A To compress data by removing redundant bits

B To encrypt data by scrambling bits

C To convert numbers from decimal to binary faster

D To reorder input data for efficient divide-and-conquer processing

💡 Hint

Think about how FFT processes data in stages.

Bit reversal reorders input indices to enable efficient recursive processing in FFT algorithms.

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. Changing all 0s to 1s and 1s to 0s

C. Flipping the order of bits from left to right

D. Adding 1 to the number

Solution

1. Step 1: Understand bit order

   Bits are arranged from left (most significant) to right (least significant).

2. Step 2: Reverse means flip order

   Reversing bits means the leftmost bit becomes rightmost, second leftmost becomes second rightmost, and so on.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

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

Common Mistakes:

• Confusing reversing bits with bitwise NOT
• Thinking reversing bits adds or subtracts from number
• Mixing bit shifting with reversing bits

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

easy

A. unsigned char reverseBits(unsigned char n) { return n << 1; }

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

C. unsigned char reverseBits(unsigned char n) { return ~n; }

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

Solution

1. Step 1: Analyze the correct loop logic

   The loop shifts rev left by 1, ORs with (n & 1), then shifts n right by 1. This reverses bits correctly.

2. Step 2: Check distractor options

   rev |= (n & 1) << i; n >>= 1; copies bits in same order. return ~n; is bitwise NOT, not reverse. return n << 1; shifts bits left, not reverse.

3. Final Answer:

   rev <<= 1; rev |= (n & 1); n >>= 1; -> Option D

4. Quick Check:

   Shift rev left + add bit from n = reverse bits [OK]

Hint: Shift rev left, add n's LSB, shift n right each step [OK]

Common Mistakes:

• Using bitwise NOT (~) instead of reversing bits
• Not shifting rev before adding new bit
• Shifting bits incorrectly causing wrong order

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

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

int main() {
    unsigned char x = 13; // binary 00001101
    unsigned char y = reverseBits(x);
    printf("%u", y);
    return 0;
}

medium

A. 11

B. 176

C. 101

D. 13

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 = 128 + 32 + 16 = 176 decimal.

3. Final Answer:

   176 -> Option B

4. Quick Check:

   Reverse 00001101 = 10110000 = 176 [OK]

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

Common Mistakes:

• Confusing reversed bits with original number
• Calculating decimal incorrectly from binary
• Ignoring leading zeros in binary

4. Identify the error in the following C function that attempts to reverse bits of a 4-bit number:

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

medium

A. It does not shift rev left before adding bits, so bits are not reversed

B. It shifts n left instead of right

C. It uses 8-bit loop instead of 4-bit

D. It returns rev without masking bits

Solution

1. Step 1: Analyze bit addition logic

   The code adds bits to rev using rev |= (n & 1) << i, which places bits in original order, not reversed.

2. Step 2: Understand correct reversing method

   To reverse bits, rev should be shifted left before adding new bit, not ORed at position i.

3. Final Answer:

   It does not shift rev left before adding bits, so bits are not reversed -> Option A

4. Quick Check:

   Shift rev left before adding bit to reverse [OK]

Hint: Shift rev left before OR to reverse bits correctly [OK]

Common Mistakes:

• Adding bits at same positions without shifting rev
• Confusing left and right shifts on n
• Looping wrong number of times

5. You want to reverse the bits of a 16-bit unsigned integer and then check if the reversed number is a palindrome in binary (reads the same forwards and backwards). Which approach is correct?

hard

A. Reverse bits using a loop, then compare reversed number with original

B. Check if original number equals reversed number without reversing bits

C. Reverse bits using a loop, then reverse again and compare with original

D. Shift bits left by 8 and compare with original

Solution

1. Step 1: Compute reversed bits

   Reverse bits using a loop to obtain the reversed number rev.

2. Step 2: Check if reversed is palindrome

   The reversed number is a palindrome if it reads the same forwards and backwards, i.e., rev == original (since reverse(rev) == original always holds for a correct reverse).

3. Final Answer:

   Reverse bits using a loop, then compare reversed number with original -> Option A

4. Quick Check:

   rev == original means rev is palindrome [OK]

Hint: rev == original checks if reversed bits form a palindrome [OK]

Common Mistakes:

• Thinking double reverse checks palindrome (it only verifies the reverse function)
• Trying to check palindrome without computing reversed bits
• Confusing bit reversal with simple shifts