190. Reverse Bits.md

190. Reverse Bits

思路

将给定的数的二进制进行翻转。

思路一、常规思路

定义res为32位无符号型且初始值为0，可从低位到高位依次取得给定的数的32位bit值，再用或运算赋值给res的最低位，res不断左移。
可将给定的数与一个mask进行与操作取得特定位数上的值，mask只有一位是1。可通过对mask移位(如下代码)或者对给定的数移位来达到取特定位的目的。

思路二、巧妙思路

• 1、若只有两位: ab, 则将第一位右移一位、将第二位左移一位即可得到ba;
• 2、若只有四位: abcd, 则先将前两位右移两位、后两位左移两位，再分别对两个两位进行情况1的操作即可得到dcba;
• 3、若只有八位: abcdefgh, 则先将前四位右移四位、后四位左移四位，再依次进行情况1、2的操作即可得到hgfedcba;
• ......

则针对此题的具体步骤是:

• 将前16位右移16位，将后16位左移16位;
• 将0-7、16-23位右移八位，将8-15、24-31位左移八位(最低位为31位);
• ......

C++

思路一

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        uint32_t mask = 1;
        for (uint32_t i = 0; i < 32; ++i) {
            // n & mask取得第i位
            res = (res << 1) | ((n & mask) >> i);
            mask = mask << 1;
        }
        return res;
    }
};

思路二

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};