Topics / Bit Manipulation / Q9
How do you reverse the bits of a byte or an n-bit number?
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 by32 - widthfor narrower values.
Where it shows up: LSB-first vs MSB-first serial protocols, CRC implementations ("reflected" CRCs), and FFT bit-reversed addressing.