Reverse Bits of a Number in DSA C

Mental Model

We flip the order of bits in a number so the last bit becomes first and the first becomes last.

Analogy: Imagine a row of light switches turned on or off. Reversing bits is like walking to the end of the row and flipping the switches in reverse order, so the last switch's state becomes the first in the new row.

Original bits: 0 0 0 0 1 1 0 1
Reversed bits: 1 0 1 1 0 0 0 0

Dry Run Walkthrough

Input: number: 13 (binary 00001101), reverse all 8 bits

Goal: Reverse the bits of the number so the output is the binary number with bits in reverse order

Step 1: Extract least significant bit (LSB) 1 and add it to result shifted left

result = 0b00000001, input shifts right to 00000110

Why: We start building reversed number from rightmost bit

Step 2: Extract next LSB 0 and add to result shifted left

result = 0b00000010, input shifts right to 00000011

Why: Add next bit to reversed number in next position

Step 3: Extract next LSB 1 and add to result shifted left

result = 0b00000101, input shifts right to 00000001

Why: Continue reversing bits one by one

Step 4: Extract next LSB 1 and add to result shifted left

result = 0b00001011, input shifts right to 00000000

Why: Process the last significant bit; loop continues 4 more times shifting result left and adding 0s

Result:

Reversed bits: 0b10110000 (decimal 176)
Final reversed number: 176

Annotated Code

DSA C

#include <stdio.h>
#include <stdint.h>

uint8_t reverseBits(uint8_t n) {
    uint8_t result = 0;
    for (int i = 0; i < 8; i++) {
        result <<= 1; // shift result left to make room for next bit
        result |= (n & 1); // add least significant bit of n to result
        n >>= 1; // shift n right to process next bit
    }
    return result;
}

int main() {
    uint8_t num = 13; // binary 00001101
    uint8_t reversed = reverseBits(num);
    printf("Original: %u (binary 00001101)\n", num);
    printf("Reversed: %u\n", reversed);
    return 0;
}

result <<= 1; // shift result left to make room for next bit

Shift reversed bits left to add new bit at right

result |= (n & 1); // add least significant bit of n to result

Add current least significant bit of input to reversed result

n >>= 1; // shift n right to process next bit

Move to next bit of input number

Output

Original: 13 (binary 00001101)

Reversed: 176

Complexity Analysis

Time: O(1) because we always process a fixed number of bits (8 bits for uint8_t)

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: This bitwise approach is much faster and uses less memory than converting to string and reversing

Edge Cases

number is 0

Reversed bits remain 0

DSA C

for (int i = 0; i < 8; i++) {

number is 255 (all bits 1)

Reversed bits remain 255

DSA C

for (int i = 0; i < 8; i++) {

When to Use This Pattern

When you need to reverse the order of bits in a number, use bitwise shifting and masking to build the reversed number bit by bit.

Common Mistakes

Mistake: Shifting the input number left instead of right when extracting bits
Fix: Shift the input number right to process bits from least significant to most significant

Mistake: Not shifting the result left before adding the new bit
Fix: Always shift the result left to make room for the next bit before adding it

Summary

Reverses the bits of a number by extracting bits one by one and building a new number in reverse order.

Use when you need to flip the bit order of a fixed-size integer, such as in low-level data processing.

The key insight is to shift the result left and add the current least significant bit of the input repeatedly.

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