Reverse bits#

Levels: level-2

Data structures: bits

Practice Link#

Description#

Reverse bits of a given 32 bits unsigned integer.

Example#

1Input: 00000010100101000001111010011100
2Output: 00111001011110000010100101000000
3Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Follow up#

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

Thinking#

We first intitialize result to 0. We then iterate from 0 to 31 (an integer has 32 bits).
In each iteration:
- We first shift result to the left by 1 bit.
- Then, if the last digit of input n is 1, we add 1 to result.
- To find the last digit of n, we just do: (n & 1) Example, if n=5 (101), n&1 = 101 & 001 = 001 = 1; however, if n = 2 (10), n&1 = 10 & 01 = 00 = 0).
- Finally, we update n by shifting it to the right by 1 (n »= 1). This is because the last digit is already taken care of, so we need to drop it by shifting n to the right by 1.
At the end of the iteration, we return result.

Python Solution#

 1class Solution:
 2    # @param n, an integer
 3    # @return an integer
 4    def reverseBits(self, n):
 5        res = 0
 6        for _ in range(32):
 7            res = (res << 1) + (n & 1)
 8            n >>= 1
 9        return res
10
11    # Use bit hacks to directly do in O(1)
12    # for 8 bit binary number abcdefgh, the process is as follow:
13    # abcdefgh -> efghabcd -> ghefcdab -> hgfedcba
14    def reverseBitsHack(self, n):
15        n = (n >> 16) | (n << 16)
16        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
17        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
18        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
19        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
20        return n