</>EmbeddedInterview

How do you reverse the bits of a byte or an n-bit number?

EasyBit Manipulation

Short answer: Loop over the bits: if bit i is set in the input, set bit (width - 1 - i) in the output. The width must be the number of bits, not bytes.

#include <stdint.h>

uint32_t reverse_n_bits(uint32_t a, unsigned width)   /* width = 1..32 */
{
    uint32_t out = 0;
    for (unsigned i = 0; i < width; i++) {
        if (a & (1u << i))
            out |= 1u << (width - 1 - i);
    }
    return out;
}

/* reverse_n_bits(15, 8)   = 0xF0  (0b00001111 -> 0b11110000) */
/* reverse_n_bits(1, 32)   = 0x80000000 */

A common bug. This version looks right but is wrong:

unsigned int a = 1;
int n = sizeof(a);            /* 4 -- that is BYTES, not bits */
for (int i = 0; i < n; i++)
    if (a & (1U << i)) temp |= 1U << ((n - 1) - i);
/* prints 8 instead of 2147483648 */

sizeof returns bytes. Use sizeof(a) * CHAR_BIT (from <limits.h>), which is 32.

Shift-in version (no reverse index, often clearer):

uint8_t reverse_byte(uint8_t b)
{
    uint8_t r = 0;
    for (int i = 0; i < 8; i++) {
        r = (uint8_t)((r << 1) | (b & 1u));  /* take LSB of b, push into r */
        b >>= 1;
    }
    return r;
}

Faster options

  • 256-entry lookup table for bytes: one memory read.
  • Swap halves, then quarters, then pairs: b = (b >> 4) | (b << 4); b = ((b & 0xCC) >> 2) | ((b & 0x33) << 2); b = ((b & 0xAA) >> 1) | ((b & 0x55) << 1);
  • On Cortex-M3 and later, __RBIT() reverses 32 bits in one instruction; shift right by 32 - width for narrower values.

Where it shows up: LSB-first vs MSB-first serial protocols, CRC implementations ("reflected" CRCs), and FFT bit-reversed addressing.