[LeetCode 190] Reverse Bits

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?

Diffculty
Hard

Similar Problems
[LeetCode 7] Reverse Integer Easy

Analysis

位操作Bit Operation，LeetCode中有关位操作的题也有不少， 比如 Repeated DNA Sequences 求重复的DNA序列， Single Number 单独的数字, Single Number II 单独的数字之二 ，和 Grey Code 格雷码 等等。 跟上面那些题比起来，这道题简直不能再简单了。 对于这道题，我们只需要把要翻转的数从右向左一位位的取出来，然后加到新生成的数的最低位即可， 代码如下：

class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for (int i = 0; i < 32; ++i) { if (n & 1 == 1) { res = (res << 1) + 1; } else { res = res << 1; } n = n >> 1; } return res; } };

下面这种写法让代码更简洁一些:

// 8 ms class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for (int i = 0; i < 32; ++i) { res |= ((n >> i) & 1) << (31 - i); } return res; } };

// 4ms class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t m = 0; for (int i = 0; i< 32 ; i++, n /= 2) m = (m << 1) + (n % 2); return m; } };

// 4 ms class Solution { public: uint32_t reverseBits(uint32_t n){ n = ((n << 16) | (n >> 16)); //swap [31:16]<=>[15:0] n = ((n & 0x00ff00ff) << 8 | (n & 0xff00ff00) >> 8); //swap [31:24]<=>[23:16] , [15:8]<=>[7:0] n = ((n & 0x0f0f0f0f) << 4 | (n & 0xf0f0f0f0) >> 4); //swap ... n = ((n & 0x33333333) << 2 | (n & 0xcccccccc) >> 2); //swap ... n = ((n & 0x55555555) << 1 | (n & 0xaaaaaaaa) >> 1); //swap ... return n;
} };

// https://leetcode.com/discuss/27338/8ms-c-code-some-ideas-about-optimization-spoiler The key idea of the optimization is to look up a 4 bit chuck and find out what the reverse is. For example, reverse of 0001 is 1000 (in decimal reverse of 1 is 8). Another example, reverse of 1010 is 0101, meaning reverse of 10 is 5. Based on this idea we could create a look up table: value -> reverse

0 ------> 0 1 ------> 8 ... ------> ... 15 ------> 15

This can be further optimized by using bytes lookup table of size 256 but I am too lazy to generate the table : ). Note, place the table initialization outside the reverseBits() routine is necessary for performance.

In theory, using look up table may improve the performance as we are dealing with 4 bits each time. Comparing to the method that iteratively swaps two bits each time, the method below should be faster. Given the 600 test cases, the performance difference is not dramatic though.

During each iteration, shift the output 4 bits to the left, and discard the lowest 4 bits from the input. Make sure the reverse of current lowest 4 bits is saved to the current highest 4 bits in the output.

char tb[16] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

uint32_t reverseBits(uint32_t n) { int curr = 0; uint32_t ret = 0; uint32_t msk = 0xF; for(int i = 0; i< 8; i++) { ret = ret << 4; curr = msk&n; ret |= tb[curr]; n = n >> 4; } return ret; }