Reverse bits

Overview

Reversing a word's bit order — bit 0 becomes bit 31, bit 1 becomes bit 30, and so on — is a small exercise with a big lesson in loop invariants. The straightforward method builds the answer one bit at a time: shift the result left to make room, OR in the low bit of the input, then shift the input right. After exactly width iterations the input is exhausted and the result holds the mirrored value. The subtlety is that the loop must run the full width even when the input reaches zero early, or the remaining shifts never happen and the answer comes out shifted toward the wrong end.

Why it matters

Bit order is a real interoperability concern. Some serial protocols transmit least-significant-bit first while your data is most-significant-bit first; certain CRC variants are defined over reflected input and output; graphics and DSP code reverse index bits for FFT butterflies. When two systems disagree about bit order the data is not corrupted so much as mirrored, which is confusing to debug unless you recognise the pattern.

Core concepts

Build from the bottom up. Start with r = 0. Each iteration: r = (r << 1) | (x & 1u); then x >>= 1;. The first input bit read ends up pushed furthest left by the remaining shifts, which is exactly the reversal.

The fixed trip count. Loop exactly 32 times for a 32-bit value — not while (x). If the input's high bits are zero, an early exit leaves the result under-shifted, so reverse(1) would return 1 instead of 0x80000000.

Why unsigned. x >>= 1 on a signed negative value sign-extends, feeding 1s in from the left forever. uint32_t makes the shift a plain logical shift.

Self-inverse. Reversing twice returns the original value — a free correctness check to assert in tests.

Faster alternatives exist. Production code often uses a byte lookup table or a divide-and-conquer swap (swap odd/even bits, then pairs, then nibbles, then bytes) in O(log n) steps. Understand the simple loop first; it is the reference implementation you test the clever one against.

Syntax notes

#include <stdint.h>

uint32_t reverse_bits(uint32_t x) {
    uint32_t r = 0;
    for (int i = 0; i < 32; i++) {   // fixed 32 iterations — not `while (x)`
        r = (r << 1) | (x & 1u);     // make room, take the low bit
        x >>= 1;                     // consume it
    }
    return r;
}

Key points:

• The trip count is the type's width, always.
• uint32_t (not int) so >> is a logical shift.
• reverse_bits(reverse_bits(x)) == x — assert this in your tests.

Lesson

Reversing bits maps bit i to bit n-1-i. The straightforward method shifts a result left while feeding in the source's low bit, n times. Reversal is an involution: doing it twice returns the original.

The demo reverses a 32-bit value and checks the round-trip.

Code examples

#include <stdio.h>
#include <stdint.h>
static uint32_t reverse_bits(uint32_t x){ uint32_t r=0; for(int i=0;i<32;i++){ r=(r<<1)|(x&1u); x>>=1; } return r; }
int main(void){
    uint32_t x = 0x0000000Fu;
    printf("0x%08X reversed = 0x%08X\n", x, reverse_bits(x));
    printf("involution check: 0x%08X\n", reverse_bits(reverse_bits(0x12345678u)));
    return 0;
}

Line by line

Common mistakes

Stopping the loop when x reaches zero instead of running the full 32 iterations — reverse(1) then returns 1 rather than 0x80000000, because the remaining left-shifts never happen. Reversing a signed value, so >> sign-extends and feeds in 1s. Confusing bit reversal with byte-order swapping (htonl) — they are different operations.

Debugging tips

Compiler errors and warnings:

• warning: right shift count >= width of type — your loop bound exceeds 32.
• -Wsign-compare between int i and an unsigned bound; keep the counter int and the bound a literal.

Runtime symptoms:

• reverse(1) returns 1. You used while (x) instead of a fixed 32 iterations — the classic bug here.
• The loop hangs or returns all 1s. x is a signed negative value; >> is sign-extending. Use uint32_t.
• Everything is off by one position. You shifted r after ORing instead of before, or shifted x before reading its low bit. Order is: shift r, OR in x & 1, then shift x.
• Only 8 bits reverse. You reversed a uint8_t but printed it as 32-bit, or looped 8 times on a 32-bit value.

Technique: test the identities first — reverse(0) == 0, reverse(0xFFFFFFFF) == 0xFFFFFFFF, reverse(1) == 0x80000000, and reverse(reverse(x)) == x for random x.

Memory safety

• Signed right shift. The dominant hazard: >> on a signed negative value is implementation-defined (arithmetic in practice), which breaks the algorithm. Use uint32_t throughout.
• Width must match the type. Looping 32 times on a uint64_t, or 64 on a uint32_t, silently produces wrong answers — the second case is also an undefined over-width shift. Tie the trip count to the type (sizeof(x) * CHAR_BIT).
• Promotion of narrow types. Reversing a uint8_t by this loop promotes to int; mask back with & 0xFFu and loop only 8 times, or the result carries stray high bits.
• No memory involved. There is nothing to allocate or free here — the risks are all in shift semantics.

Real-world uses

Concrete uses: CRC-32 as used by Ethernet and zlib is defined over reflected input and output, so implementations reverse bits (or bake the reflection into the table). Some SPI and I²C peripherals clock out LSB-first while the host stores MSB-first. FFT implementations permute samples by reversed index. Barcode and RFID encodings sometimes specify reversed bit order.

Professional best practices:

Beginner:

• Write the simple fixed-count loop and keep it as your reference implementation.
• Assert the self-inverse property in tests.

Intermediate:

• If profiling justifies it, switch to a 256-entry byte table or the divide-and-conquer swap — and validate it against the simple loop over random inputs.
• Derive the trip count from sizeof(x) * CHAR_BIT so the function cannot silently mismatch its type.
• Do not confuse bit reversal with byte-order swapping (htonl); they are different operations and mixing them up produces very confusing bugs.

Practice tasks

1. (Beginner) Reverse 32 bits. Implement uint32_t reverse_bits(uint32_t x) with the fixed-count loop. Example: 1 → 0x80000000; 0x80000000 → 1. Concepts: accumulate-and-shift, fixed trip count.

2. (Beginner) Prove the self-inverse. Write a test asserting reverse_bits(reverse_bits(x)) == x for 1,000 pseudo-random values plus 0, 1 and 0xFFFFFFFF. Concepts: property testing.

3. (Intermediate) Reverse a byte. Implement uint8_t reverse_byte(uint8_t b) looping 8 times, and confirm 0b00000001 → 0b10000000. Hint: mask the result back to 8 bits after promotion. Concepts: integer promotion, width discipline.

4. (Intermediate) Table-driven reversal. Precompute a 256-entry table of reversed bytes, then reverse a uint32_t as four table lookups in swapped order. Requirements: must agree with the loop version for every tested input. Concepts: lookup tables, validating an optimisation against a reference.

Summary

Reversal builds the answer one bit at a time — shift the result left, OR in the input's low bit, shift the input right — repeated for exactly the type's width. The fixed trip count is the crux: exiting early when the input hits zero leaves the result under-shifted, so reverse(1) must run all 32 passes to become 0x80000000. Keep the value uint32_t so the right shift is logical rather than sign-extending, assert the self-inverse property in tests, and treat the simple loop as the reference you validate any faster table-driven version against.

Practice with these exercises

• Reverse 32 bits
• Reverse a byte