</>EmbeddedInterview
← All problems · Bit Manipulation

Reverse the Bits of a 32-bit Integer

Easy

Implement uint32_t reverse_bits(uint32_t n) that mirrors all 32 bits: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on.

Example: 0x0000000F → 0xF0000000; 0x00000001 → 0x80000000.

Write the simple loop first, then the constant-time version interviewers ask for next.

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

Loop 32 times: shift the result left to make room, copy the lowest bit of n into it, then shift n right.

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

/* Simple version: 32 iterations */
uint32_t reverse_bits(uint32_t n)
{
    uint32_t rev = 0;
    for (int i = 0; i < 32; i++) {
        rev = (rev << 1) | (n & 1u);   /* append lowest bit of n */
        n >>= 1;
    }
    return rev;
}

/* Constant-time version: swap ever-larger groups (also correct) */
uint32_t reverse_bits_fast(uint32_t n)
{
    n = ((n & 0x55555555u) << 1) | ((n >> 1) & 0x55555555u);  /* swap single bits */
    n = ((n & 0x33333333u) << 2) | ((n >> 2) & 0x33333333u);  /* swap pairs       */
    n = ((n & 0x0F0F0F0Fu) << 4) | ((n >> 4) & 0x0F0F0F0Fu);  /* swap nibbles     */
    n = ((n & 0x00FF00FFu) << 8) | ((n >> 8) & 0x00FF00FFu);  /* swap bytes       */
    return (n << 16) | (n >> 16);                              /* swap halves      */
}

Both of your versions are correct.

Loop version: each iteration takes the lowest bit off n and pushes it onto the right of rev. After 32 steps, the bit that started at position 0 has been shifted left 31 times, so it ends at position 31. It must run all 32 iterations even when n becomes 0 early, otherwise leading bits are lost.

Walk-through on 4 bits, n = 0b0011

i n & 1 rev n after
0 1 0001 0001
1 1 0011 0000
2 0 0110 0000
3 0 1100 0000

Fast version: five swap stages of width 1, 2, 4, 8 and 16 bits. Each stage uses a mask to select one half of every group, moves it by the group width and merges. That is about 15 operations with no loop or branch, which is O(log w) for a w-bit word.

On real hardware: Armv7-M and later have a single instruction, RBIT (__RBIT() in CMSIS); Clang also provides __builtin_bitreverse32. A 256-entry byte table is another fast option when flash is available.

Small fixes worth mentioning: use 1u and u-suffixed masks so all arithmetic is unsigned, and print a uint32_t with "%08" PRIX32 from <inttypes.h> rather than %08X, which assumes unsigned int is 32 bits.

Where it is used: LSB-first vs MSB-first peripherals, CRC implementations with reflected polynomials, and FFT bit-reversed addressing.

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(reverse_bits(0x0000000Fu) == 0xF0000000u);
    CHECK(reverse_bits(0x00000001u) == 0x80000000u);
    CHECK(reverse_bits(0x80000000u) == 0x00000001u);
    CHECK(reverse_bits(0x00000000u) == 0x00000000u);
    CHECK(reverse_bits(0xFFFFFFFFu) == 0xFFFFFFFFu);
    CHECK(reverse_bits(0x12345678u) == 0x1E6A2C48u);
    CHECK(reverse_bits(reverse_bits(0xDEADBEEFu)) == 0xDEADBEEFu);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}