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.