How do you reverse the bits of a 32-bit integer?
Short answer: Swap progressively larger groups of bits (1, 2, 4, 8, then 16) using masks. It runs in constant time with no loop. On Cortex-M3 and later it is a single RBIT instruction.
uint32_t reverse_bits(uint32_t x)
{
x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1); /* swap adjacent bits */
x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2); /* swap bit pairs */
x = ((x >> 4) & 0x0F0F0F0Fu) | ((x & 0x0F0F0F0Fu) << 4); /* swap nibbles */
x = ((x >> 8) & 0x00FF00FFu) | ((x & 0x00FF00FFu) << 8); /* swap bytes */
return (x >> 16) | (x << 16); /* swap 16-bit halves */
}
How the masks work: 0x5 is 0101, so 0x55555555 selects the even bits and 0xAAAAAAAA the odd bits. 0x3 = 0011 selects the low pair in each nibble, and 0x0F the low nibble in each byte. Each line moves the selected group up and the other group down.
Example: reverse_bits(0x00000001) == 0x80000000; reverse_bits(0x0000000F) == 0xF0000000.
Cost: 5 steps for 32 bits (log₂ 32), versus 32 iterations for the loop version.
Using the hardware:
#include "cmsis_compiler.h"
uint32_t r = __RBIT(x); /* Cortex-M3/M4/M7/M33 */
GCC also has __builtin_bitreverse32 in recent versions (Clang has had it for longer).
Follow-up: "Reverse only the lower k bits?" reverse_bits(x) >> (32 - k) for 1 ≤ k ≤ 32 (handle k == 32 without the shift, because shifting by 0 is fine but shifting by 32 is not).