[LeetCode] 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 10101111110010110010011101101001.

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?

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

這道題又是在考察位操作 Bit Operation，LeetCode 中有關(guān)位操作的題也有不少，比如 Repeated DNA Sequences，Single Number,   Single Number II ，和 Grey Code 等等。跟上面那些題比起來，這道題簡直不能再簡單了，我們只需要把要翻轉(zhuǎn)的數(shù)從右向左一位位的取出來，如果取出來的是1，將結(jié)果 res 左移一位并且加上1；如果取出來的是0，將結(jié)果 res 左移一位，然后將n右移一位即可，參見代碼如下：

解法一：

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

我們可以簡化上面的代碼，去掉 if...else... 結(jié)構(gòu)，可以結(jié)果 res 左移一位，然后再判斷n的最低位是否為1，是的話那么結(jié)果 res 加上1，然后將n右移一位即可，代碼如下：

解法二：

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

我們繼續(xù)簡化上面的解法，將 if 判斷句直接揉進去，通過 ‘或' 上一個n的最低位即可，用n ‘與' 1提取最低位，然后將n右移一位即可，代碼如下：

解法三：

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

博主還能進一步簡化，這里不更新n的值，而是直接將n右移i位，然后通過 ‘與' 1來提取出該位，加到左移一位后的結(jié)果 res 中即可，參加代碼如下：

解法四：

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

我們也可以換一種角度來做，首先將n右移i位，然后通過 ‘與' 1來提取出該位，然后將其左移 (32 - i) 位，然后 ‘或' 上結(jié)果 res，就是其顛倒后應(yīng)該在的位置，參見代碼如下： 

解法五：

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/190

類似題目：

Number of 1 Bits

Reverse Integer

參考資料：

https://leetcode.com/problems/reverse-bits/

https://leetcode.com/problems/reverse-bits/discuss/54938/A-short-simple-Java-solution

https://leetcode.com/problems/reverse-bits/discuss/54772/The-concise-C++-solution(9ms)

https://leetcode.com/problems/reverse-bits/discuss/54741/O(1)-bit-operation-C++-solution-(8ms)

https://leetcode.com/problems/reverse-bits/discuss/54738/Sharing-my-2ms-Java-Solution-with-Explanation

https://leetcode.com/problems/reverse-bits/discuss/54873/Java-two-methods-using-String-or-bit-operation-6ms-and-2ms-easy-understand

到此這篇關(guān)于C++實現(xiàn)LeetCode(190.顛倒二進制位)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)顛倒二進制位內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論