FXTi's blog
0%

reverse-bits

Posted on Edited on

Reverse Bits – LeetCode 190

Problem

Description

Reverse bits of a given 32 bits unsigned integer.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t r = 0;
        for(unsigned i = 0; i != 32; ++i, n >>= 1){
            r |= n & 0x1;
            r <<= 1;
        }
        return r;
    }
};

思路

简单的逐位翻转。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$76.23\%$

Batter

思路

分治法，先是反转2个，再依次放大翻转单元，时间复杂度$O(log_{2}{n})$，空间复杂度$O(1)$。
耗时$3$ ms，排名$76.23\%$

Code

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 & 0x55555555) << 1);
        n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
        n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
        n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
        n = ( n >> 16             ) | ( n               << 16);
        return n;
    }
};