C++實現LeetCode(190.顛倒二進制位)

Posted on by

[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 中有關位操作的題也有不少，比如 Repeated DNA Sequences，Single Number,   Single Number II ，和 Grey Code 等等。跟上面那些題比起來，這道題簡直不能再簡單瞭，我們隻需要把要翻轉的數從右向左一位位的取出來，如果取出來的是1，將結果 res 左移一位並且加上1；如果取出來的是0，將結果 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… 結構，可以結果 res 左移一位，然後再判斷n的最低位是否為1，是的話那麼結果 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;
    }
};

我們繼續簡化上面的解法，將 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來提取出該位，加到左移一位後的結果 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) 位，然後 ‘或’ 上結果 res，就是其顛倒後應該在的位置，參見代碼如下： 

解法五：

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

到此這篇關於C++實現LeetCode(190.顛倒二進制位)的文章就介紹到這瞭,更多相關C++實現顛倒二進制位內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：