</>EmbeddedInterview
← All problems · Bit Manipulation

Swap Odd and Even Bits

Easy

Implement uint32_t swap_odd_even_bits(uint32_t n) that swaps every pair of adjacent bits: bit 0 with bit 1, bit 2 with bit 3, and so on.

Example: 23 (binary 0001 0111) → 43 (binary 0010 1011).

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

0x55555555 has a 1 in every even position (0, 2, 4…) and 0xAAAAAAAA in every odd position. Pick out each set, move it one place towards the other, and combine.

#include <stdio.h>
#include <stdint.h>

uint32_t swap_odd_even_bits(uint32_t n)
{
    uint32_t even = n & 0x55555555u;   /* bits 0, 2, 4, ... */
    uint32_t odd  = n & 0xAAAAAAAAu;   /* bits 1, 3, 5, ... */
    return (even << 1) | (odd >> 1);
}

Your version is correct. Each even bit moves up one position into the odd slot next to it, and each odd bit moves down. Because the two masks never overlap, OR-ing the shifted halves cannot collide. It runs in a fixed handful of instructions, with no loop.

Walk-through: n = 23 = 0b0001 0111

step binary value
n 0001 0111 23
even = n & 0x55 0001 0101 21
odd = n & 0xAA 0000 0010 2
even << 1 0010 1010 42
odd >> 1 0000 0001 1
result 0010 1011 43

Why 0x55 and 0xAA: 0x5 is 0101 and 0xA is 1010, so repeating them gives the even-bit and odd-bit masks for any width.

Points to mention: - Use unsigned types: with a signed int, 0xAAAAAAAA does not fit and >> of a negative value is implementation-defined. - This is exactly the first stage of the fast bit-reversal (see Reverse the Bits of a 32-bit Integer). Swapping pairs with 0x33333333, nibbles with 0x0F0F0F0F and bytes with 0x00FF00FF are the other stages. - Follow-up: swap nibbles in a byte, (b << 4) | (b >> 4), which is used to convert BCD and some LCD controller data.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    CHECK(swap_odd_even_bits(23) == 43);
    CHECK(swap_odd_even_bits(1) == 2);
    CHECK(swap_odd_even_bits(2) == 1);
    CHECK(swap_odd_even_bits(0xAAAAAAAAu) == 0x55555555u);
    CHECK(swap_odd_even_bits(0x55555555u) == 0xAAAAAAAAu);
    CHECK(swap_odd_even_bits(0x80000000u) == 0x40000000u);
    CHECK(swap_odd_even_bits(0xFFFFFFFFu) == 0xFFFFFFFFu);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}