</>EmbeddedInterview

How do you reverse the bits of a 32-bit integer?

MediumBit Manipulation

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).