Topics / Bit Manipulation / Q11
How do you swap the odd and even bits of a number?
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.