C Program to Reverse Bits of a Number

To reverse bits of a number in C, use a loop to extract each bit with n & 1, shift the result left, and add the bit; repeat for all bits. Example code: unsigned int reverseBits(unsigned int n) { unsigned int rev = 0; for (int i = 0; i < 32; i++) { rev <<= 1; rev |= (n & 1); n >>= 1; } return rev; }

Examples

Input0

Output0

Input13

Output2952790016

Input4294967295

Output4294967295

How to Think About It

To reverse bits of a number, think of reading the bits from right to left and building a new number by placing these bits from left to right. Extract the least significant bit using n & 1, add it to the reversed number after shifting it left, then shift the original number right to process the next bit. Repeat this for all bits in the number.

Algorithm

1

Get the input number.

2

Initialize a variable to store the reversed bits as 0.

3

Repeat for the total number of bits (usually 32):

4

Shift the reversed variable left by 1 to make space for the next bit.

5

Extract the least significant bit of the input number using bitwise AND with 1.

6

Add this bit to the reversed variable using bitwise OR.

7

Shift the input number right by 1 to process the next bit.

8

Return the reversed variable.

Code

c

#include <stdio.h>

unsigned int reverseBits(unsigned int n) {
    unsigned int rev = 0;
    for (int i = 0; i < 32; i++) {
        rev <<= 1;
        rev |= (n & 1);
        n >>= 1;
    }
    return rev;
}

int main() {
    unsigned int num = 13;
    unsigned int reversed = reverseBits(num);
    printf("Original: %u\nReversed bits: %u\n", num, reversed);
    return 0;
}

Output

Original: 13
Reversed bits: 2952790016

Dry Run

Let's trace the number 13 through the code to see how bits are reversed.

1

Initial values

n = 13 (binary 00000000000000000000000000001101), rev = 0

2

Iteration 1

rev <<= 1 -> 0, n & 1 = 1, rev |= 1 -> rev = 1, n >>= 1 -> n = 6

3

Iteration 2

rev <<= 1 -> 2, n & 1 = 0, rev |= 0 -> rev = 2, n >>= 1 -> n = 3

4

Iteration 3

rev <<= 1 -> 4, n & 1 = 1, rev |= 1 -> rev = 5, n >>= 1 -> n = 1

5

Iteration 4

rev <<= 1 -> 10, n & 1 = 1, rev |= 1 -> rev = 11, n >>= 1 -> n = 0

6

Iterations 5 to 32

rev <<= 1 and rev |= 0 (since n is 0), rev shifts left each time

7

Final result

rev = 2952790016 (binary 10110000000000000000000000000000)

Iteration	rev (decimal)	rev (binary)	n (decimal)	n (binary)
1	1	00000000000000000000000000000001	6	00000000000000000000000000000110
2	2	00000000000000000000000000000010	3	00000000000000000000000000000011
3	5	00000000000000000000000000000101	1	00000000000000000000000000000001
4	11	00000000000000000000000000001011	0	00000000000000000000000000000000
5	22	00000000000000000000000000010110	0	00000000000000000000000000000000
6	44	00000000000000000000000000101100	0	00000000000000000000000000000000
7	88	00000000000000000000000001011000	0	00000000000000000000000000000000
8	176	00000000000000000000000010110000	0	00000000000000000000000000000000
9	352	00000000000000000000000101100000	0	00000000000000000000000000000000
10	704	00000000000000000000001011000000	0	00000000000000000000000000000000
11	1408	00000000000000000000010110000000	0	00000000000000000000000000000000
12	2816	00000000000000000000101100000000	0	00000000000000000000000000000000
13	5632	00000000000000000001011000000000	0	00000000000000000000000000000000
14	11264	00000000000000000010110000000000	0	00000000000000000000000000000000
15	22528	00000000000000000101100000000000	0	00000000000000000000000000000000
16	45056	00000000000000001011000000000000	0	00000000000000000000000000000000
17	90112	00000000000000010110000000000000	0	00000000000000000000000000000000
18	180224	00000000000000101100000000000000	0	00000000000000000000000000000000
19	360448	00000000000001011000000000000000	0	00000000000000000000000000000000
20	720896	00000000000010110000000000000000	0	00000000000000000000000000000000
21	1441792	00000000000101100000000000000000	0	00000000000000000000000000000000
22	2883584	00000000001011000000000000000000	0	00000000000000000000000000000000
23	5767168	00000000010110000000000000000000	0	00000000000000000000000000000000
24	11534336	00000000101100000000000000000000	0	00000000000000000000000000000000
25	23068672	00000001011000000000000000000000	0	00000000000000000000000000000000
26	46137344	00000010110000000000000000000000	0	00000000000000000000000000000000
27	92274688	00000101100000000000000000000000	0	00000000000000000000000000000000
28	184549376	00001011000000000000000000000000	0	00000000000000000000000000000000
29	369098752	00010110000000000000000000000000	0	00000000000000000000000000000000
30	738197504	00101100000000000000000000000000	0	00000000000000000000000000000000
31	1476395008	01011000000000000000000000000000	0	00000000000000000000000000000000
32	2952790016	10110000000000000000000000000000	0	00000000000000000000000000000000

Why This Works

Step 1: Extracting bits

Using n & 1 extracts the least significant bit of the number, which is the rightmost bit.

Step 2: Building reversed number

Shift the reversed number left by 1 to make space, then add the extracted bit using |= to place it in the correct reversed position.

Step 3: Shifting input

Shift the input number right by 1 to move to the next bit to process in the next loop iteration.

Alternative Approaches

Using recursion

c

#include <stdio.h>

unsigned int reverseBitsRec(unsigned int n, int bits) {
    if (bits == 0) return 0;
    return ((n & 1) << (bits - 1)) | reverseBitsRec(n >> 1, bits - 1);
}

int main() {
    unsigned int num = 13;
    unsigned int reversed = reverseBitsRec(num, 32);
    printf("Original: %u\nReversed bits: %u\n", num, reversed);
    return 0;
}

Recursion is elegant but may use more stack memory and be slower than iteration.

Using lookup table for bytes

c

#include <stdio.h>

unsigned char reverseByte(unsigned char b) {
    b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
    b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
    b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
    return b;
}

unsigned int reverseBits(unsigned int n) {
    return (reverseByte(n & 0xFF) << 24) |
           (reverseByte((n >> 8) & 0xFF) << 16) |
           (reverseByte((n >> 16) & 0xFF) << 8) |
           (reverseByte((n >> 24) & 0xFF));
}

int main() {
    unsigned int num = 13;
    unsigned int reversed = reverseBits(num);
    printf("Original: %u\nReversed bits: %u\n", num, reversed);
    return 0;
}

Using byte-wise reversal with bit tricks is faster but more complex to understand.

Complexity: O(1) time, O(1) space

Time Complexity

The loop runs a fixed 32 times for 32-bit integers, so the time is constant O(1).

Space Complexity

Only a few variables are used, so space complexity is O(1).

Which Approach is Fastest?

The iterative bit-shifting method is simple and fast. The lookup table method can be faster for repeated calls but uses more code. Recursion is slower and uses more stack.

Approach	Time	Space	Best For
Iterative bit-shifting	O(1)	O(1)	Simple and fast for single calls
Recursion	O(1)	O(1) stack	Elegant but less efficient
Lookup table byte-wise	O(1)	O(1)	Fastest for repeated calls, more complex