C++中怎么利用LeetCode顛倒二進制位

C++中怎么利用LeetCode顛倒二進制位，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

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

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。