1 190.颠倒二进制位

方法一：逐位颠倒法

• uint32_t rev = 0; 声明rev变量用32位无符号类型存储；
• (n & 1) 取最后一位：将n与（000000000000000000000000000000000001）按位并；
• (n & 0) 对最后一位取反：
• << (31 - i); 左移31-i位
• 移位运算比按位或/并优先级高；
• n >>= 1; n右移一位后赋值给n【n = n >> 1】如果只是n >> 1程序将出错，因为n的值始终不变

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

方法二：位运算分治法

• (n >> 1) & M1：将偶数位右移至奇数位，由于奇数位均为1，偶数位均为0，取并操作，即奇数位（原偶数位）保持不变，偶数位均归零；
• (n & M1) << 1：原奇数位保持不变，偶数位归零，左移一位，即原奇数位换为偶数位；

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 1) & M1 | (n & M1) << 1;
        n = (n >> 2) & M2 | (n & M2) << 2;
        n = (n >> 4) & M3 | (n & M3) << 4;
        n = (n >> 8) & M4 | (n & M4) << 8;
        return n >> 16 | n << 16;
    }

private:
    const uint32_t M1 = 0x55555555; // 0101 0101 0101 0101 0101 0101 0101 0101
    const uint32_t M2 = 0x33333333; // 0011 0011 0011 0011 0011 0011 0011 0011
    const uint32_t M3 = 0x0f0f0f0f; // 0000 1111 0000 1111 0000 1111 0000 1111
    const uint32_t M4 = 0x00ff00ff; // 0000 0000 1111 1111 0000 0000 1111 1111
};