LeetCode Reverse Bits

LeetCode 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?

Related problem: Reverse Integer


本题要把一个无符号32位整数的二进制位翻转,因为之前刚刷过LeetCode Number of 1 Bits可以快速统计uint32中二进制1的个数,所以很快联想到解法。一个32次的循环,依次获取到原数字的每一个二进制位,然后和结果取或,结果依次左移。

完整代码如下:

class Solution {
public:
	uint32_t reverseBits(uint32_t n) {
		uint32_t ans = 0;
		for (int i = 0; i < 31; i++) {
			ans |= (n & 1);
			ans <<= 1;
			n >>= 1;
		}
		return ans | (n & 1);
	}
};

本代码提交AC,用时3MS。

有意思的是Follow up,说如果这个函数会被多次调用,该怎样优化。都提到会被多次调用了,那肯定是把之前计算过的结果保存起来,下次查询的时候直接调用。但是一个32位的数,一共有2^32种情况,多次调用遇到同一个数的概率有点低,如果把之前的结果当成一个缓存,则缓存命中的概率有点低。如果只是缓存4bit的结果,只有2^4=16种情况,命中的概率就大大提高了。

这个解法就是直接缓存了4bit的翻转结果,放到tb数组中。每次取出原数字的4bit,然后直接查tb表,得到4bit的翻转结果,和ret取或,这样for循环只执行了8次。不错。

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;
}

还有一种解法借鉴了归并排序的思路,假设要对一个8bit的数组归并排序,先要不断一分为二,在归并的时候,在最底层对每1bit-1bit的对归并排序,倒数第二层对每2bit-2bit的对归并排序,如此往上归并。

      01101001
    /         \
   0110      1001
  /   \     /   \
 01   10   10   01
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

逆序也可以借鉴归并的思路,如下,首先最底层对每相邻的1bit-1bit交换位置,然后倒数第二层,对每相邻的2bit-2bit交换位置,如此往上交换,得到序列10010110,正好是上图中01101001的逆序。

      10010110
    /         \
   0110      1001
  /   \     /   \
 10   01   01   10
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

这个思路的代码如下,没有了for循环,只需执行20次位运算,代码中用8bit的字符串模拟了执行的情况。

class Solution {
public:
	uint32_t reverseBits(uint32_t x) { // x = ABCDEFGH
		x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); // x = B0D0F0H0 | 0A0C0E0G = BADCFEHG
		x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); // x = DC00HG00 | 00BA00FE = DCBAHGFE
		x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); // x = HGFE0000 | 0000DCBA = HGFEDCBA
		x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); // ...
		x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
		return x;
	}
};

上面的16进制数字中:
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
0xAAAAAAAA = 1010 1010 1010 1010 1010 1010 1010 1010
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0xCCCCCCCC = 1100 1100 1100 1100 1100 1100 1100 1100

本代码提交AC,用时也是3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *