C++ Program to Reverse Bits of an Integer

You can reverse bits in C++ by shifting bits from the input number and building the reversed number using a loop like for (int i = 0; i < 32; i++) { reversed = (reversed << 1) | (n & 1); n >>= 1; }.

Examples

Input0

Output0

Input13

Output2952790016

Input4294967295

Output4294967295

How to Think About It

To reverse bits, think of taking the rightmost bit of the number and placing it as the leftmost bit of the result. Repeat this for all bits by shifting the input right and the result left, collecting bits one by one.

Algorithm

1

Get the input number.

2

Initialize a variable to store the reversed bits as 0.

3

Repeat 32 times (for each bit in a 32-bit integer):

4

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

5

Extract the rightmost bit of the input number and add it to reversed.

6

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

7

Return the reversed number.

Code

cpp

#include <iostream>
using namespace std;

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

int main() {
    unsigned int n = 13;
    cout << reverseBits(n) << endl;
    return 0;
}

Output

2952790016

Dry Run

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

1

Initial values

n = 13 (binary 00000000000000000000000000001101), reversed = 0

2

First iteration

reversed <<= 1 -> 0, reversed |= (13 & 1) -> 1, n >>= 1 -> 6

3

Second iteration

reversed <<= 1 -> 2, reversed |= (6 & 1) -> 2, n >>= 1 -> 3

4

Third iteration

reversed <<= 1 -> 4, reversed |= (3 & 1) -> 5, n >>= 1 -> 1

5

Fourth iteration

reversed <<= 1 -> 10, reversed |= (1 & 1) -> 11, n >>= 1 -> 0

6

Remaining iterations

reversed <<= 1 and reversed |= 0 (since n is 0), repeated 28 times

7

Final reversed value

reversed = 2952790016 (binary 10110000000000000000000000000000)

Iteration	n (binary)	n & 1	reversed (binary)
1	00000000000000000000000000001101	1	00000000000000000000000000000001
2	00000000000000000000000000000110	0	00000000000000000000000000000010
3	00000000000000000000000000000011	1	00000000000000000000000000000101
4	00000000000000000000000000000001	1	00000000000000000000000000001011
5	00000000000000000000000000000000	0	00000000000000000000000000010110
6	00000000000000000000000000000000	0	00000000000000000000000000101100
7	00000000000000000000000000000000	0	00000000000000000000000001011000
8	00000000000000000000000000000000	0	00000000000000000000000010110000
9	00000000000000000000000000000000	0	00000000000000000000000101100000
10	00000000000000000000000000000000	0	00000000000000000000001011000000
11	00000000000000000000000000000000	0	00000000000000000000010110000000
12	00000000000000000000000000000000	0	00000000000000000000101100000000
13	00000000000000000000000000000000	0	00000000000000000001011000000000
14	00000000000000000000000000000000	0	00000000000000000010110000000000
15	00000000000000000000000000000000	0	00000000000000000101100000000000
16	00000000000000000000000000000000	0	00000000000000001011000000000000
17	00000000000000000000000000000000	0	00000000000000010110000000000000
18	00000000000000000000000000000000	0	00000000000000101100000000000000
19	00000000000000000000000000000000	0	00000000000001011000000000000000
20	00000000000000000000000000000000	0	00000000000010110000000000000000
21	00000000000000000000000000000000	0	00000000000101100000000000000000
22	00000000000000000000000000000000	0	00000000001011000000000000000000
23	00000000000000000000000000000000	0	00000000010110000000000000000000
24	00000000000000000000000000000000	0	00000000101100000000000000000000
25	00000000000000000000000000000000	0	00000001011000000000000000000000
26	00000000000000000000000000000000	0	00000010110000000000000000000000
27	00000000000000000000000000000000	0	00000101100000000000000000000000
28	00000000000000000000000000000000	0	00001011000000000000000000000000
29	00000000000000000000000000000000	0	00010110000000000000000000000000
30	00000000000000000000000000000000	0	00101100000000000000000000000000
31	00000000000000000000000000000000	0	01011000000000000000000000000000
32	00000000000000000000000000000000	0	10110000000000000000000000000000

Why This Works

Step 1: Shift reversed left

We shift reversed left by 1 to make room for the next bit from n.

Step 2: Add rightmost bit

We add the rightmost bit of n to reversed using bitwise OR after masking with n & 1.

Step 3: Shift input right

We shift n right by 1 to move to the next bit for the next iteration.

Alternative Approaches

Using built-in function __builtin_bitreverse32 (GCC/Clang)

cpp

#include <iostream>
using namespace std;

unsigned int reverseBits(unsigned int n) {
    return __builtin_bitreverse32(n);
}

int main() {
    unsigned int n = 13;
    cout << reverseBits(n) << endl;
    return 0;
}

This is very fast but only works with GCC or Clang compilers supporting this builtin.

Using lookup table for bytes

cpp

#include <iostream>
using namespace std;

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 n = 13;
    cout << reverseBits(n) << endl;
    return 0;
}

This method uses bitwise tricks on bytes and combines them, which can be faster for repeated calls.

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

Time Complexity

The loop runs a fixed 32 times for a 32-bit integer, 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?

Using built-in functions like __builtin_bitreverse32 is fastest, followed by lookup table methods, then the simple loop approach.

Approach	Time	Space	Best For
Simple loop	O(1)	O(1)	Easy to understand and portable
Built-in function	O(1)	O(1)	Fastest but compiler-specific
Lookup table	O(1)	O(1)	Faster for many calls, uses more code