LeetCode Reverse Bits

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Example 1:

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

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

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


本题要把一个无符号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 *