</>EmbeddedInterview

How do you swap the odd and even bits of a number?

MediumBit Manipulation

Short answer: Mask the odd bits with 0xAAAAAAAA and shift them right by one, mask the even bits with 0x55555555 and shift them left by one, then OR the two halves.

uint32_t swap_odd_even_bits(uint32_t n)
{
    return ((n & 0xAAAAAAAAu) >> 1) | ((n & 0x55555555u) << 1);
}

Example: 23 = 0b0001_0111

n          = 0001 0111
odd bits   = 0000 0010  (n & 0xAA) -> >>1 = 0000 0001
even bits  = 0001 0101  (n & 0x55) -> <<1 = 0010 1010
result     = 0010 1011  = 43

Bit 0 and bit 1 swap, bit 2 and bit 3 swap, and so on.

Why the masks: 0xA is 1010 (bits 1 and 3 of a nibble, the odd positions) and 0x5 is 0101 (bits 0 and 2, the even positions). Repeating them covers all 32 bits.

Use unsigned. With a signed int, (n & 0xAAAAAAAA) >> 1 involves a value that may have the sign bit set, and shifting the even bits left can move a 1 into bit 31 of a signed int (undefined behaviour). With uint32_t both shifts are well-defined.

Related tricks with the same idea:

  • Swap nibbles in a byte: (b >> 4) | (b << 4).
  • Swap adjacent bytes: ((x & 0xFF00FF00u) >> 8) | ((x & 0x00FF00FFu) << 8).
  • This step is the first line of the constant-time bit-reverse algorithm.