How to Reverse Bits for 32-bit Unsigned Integer in C/C++?

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Submit your solution at: https://leetcode.com/problems/reverse-bits/

O(logn)

The O(logn) idea is to check the bits by bits for the given integer from the least significant bits (LSB) to the most significant ones (MSB). At each iteration, the bit is applied from the left to the right.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t x;
        for(auto i = 31; n; ) {
            x |= (n & 1) << i;
            n >>= 1;
            -- i;
        }
        return x;
    }
};

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t x;
        for(auto i = 31; n; ) {
            x |= (n & 1) << i;
            n >>= 1;
            -- i;
        }
        return x;
    }
};

You can write O(logn) loops in many other similar forms.

O(1) Bit Swaps

If this function is called many times, you can optimize it to O(1) constant time using bit tweaks.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 1) & 0x55555555 | (n << 1) & 0xaaaaaaaa;
        n = (n >> 2) & 0x33333333 | (n << 2) & 0xcccccccc;
        n = (n >> 4) & 0x0f0f0f0f | (n << 4) & 0xf0f0f0f0;
        n = (n >> 8) & 0x00ff00ff | (n << 8) & 0xff00ff00;
        n = (n >> 16) & 0x0000ffff | (n << 16) & 0xffff0000;
        return n;
    }
}

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 1) & 0x55555555 | (n << 1) & 0xaaaaaaaa;
        n = (n >> 2) & 0x33333333 | (n << 2) & 0xcccccccc;
        n = (n >> 4) & 0x0f0f0f0f | (n << 4) & 0xf0f0f0f0;
        n = (n >> 8) & 0x00ff00ff | (n << 8) & 0xff00ff00;
        n = (n >> 16) & 0x0000ffff | (n << 16) & 0xffff0000;
        return n;
    }
}

Basically, the idea is to swap 2 bits, then 4 bits, 8 bits and 16 bits. If a integer binary representation is (abcdefgh) then what the above does is:

abcdefgh — ba dc fe hg — dcba hgfe — hgfedcba

The bitwise and shifting operations are fast and probably all of them can be done in registers.

From the HACKERS-DELIGHT Figure 7-1, the Java function Integer.reverse() is implemented as:

1
2
3
4
5
6
7

public int reverseBits(int n) {
    // note: mutating formal parameter
    n = ((n & 0x5555_5555) << 1) | ((n >>> 1) & 0x5555_5555);
    n = ((n & 0x3333_3333) << 2) | ((n >>> 2) & 0x3333_3333);
    n = ((n & 0x0F0F_0F0F) << 4) | ((n >>> 4) & 0x0F0F_0F0F);
    return (n >>> 24) | ((n >>> 8) & 0xFF00) | ((n & 0xFF00) << 8) | (n << 24);
}

public int reverseBits(int n) {
    // note: mutating formal parameter
    n = ((n & 0x5555_5555) << 1) | ((n >>> 1) & 0x5555_5555);
    n = ((n & 0x3333_3333) << 2) | ((n >>> 2) & 0x3333_3333);
    n = ((n & 0x0F0F_0F0F) << 4) | ((n >>> 4) & 0x0F0F_0F0F);
    return (n >>> 24) | ((n >>> 8) & 0xFF00) | ((n & 0xFF00) << 8) | (n << 24);
}

Just reverse bits in pairs, then reverse pairs in quadruples, then reverse quadruples in “octuples” (well, bytes or octets), then just reverse bytes.

Optimisation by Storing the 2 Bytes Results

If you want it to be faster, you can pre-calculate the results up to 2 bytes and use the results like this:

1
2
3
4
5
6
7
8
9
10
11

// pre-calculated reverse results for up-to-2 bytes.
uint32_t map[65536];
 
// compute the cache
for (int i = 0; i <= 65535; ++i) {
    map[i] = reverseBits(i); 
}
 
uint32_t reverseBits(uint32_t n) {
    return (map[n & 0xFFFF] << 16) | map[n >>> 16];
}

// pre-calculated reverse results for up-to-2 bytes.
uint32_t map[65536];

// compute the cache
for (int i = 0; i <= 65535; ++i) {
    map[i] = reverseBits(i); 
}

uint32_t reverseBits(uint32_t n) {
    return (map[n & 0xFFFF] << 16) | map[n >>> 16];
}

Reverse Bits of 32-bit Integer:

• Teaching Kids Programming – Reverse Bits of a 32-bit Integer
• How to Reverse Bits for 32-bit Unsigned Integer in C/C++?
• GoLang: Reverse the Bits

--EOF (The Ultimate Computing & Technology Blog) --