2018-05-16 190. Reverse Bits

题意：给你一个32位无符号数（uint32_t）n，将n的二进制数反转后以32位无符号格式返回。例如：

Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100, 
             return 964176192 represented in binary as 00111001011110000010100101000000.

解题思路：
方法一：将n转换为二进制，反转后再输出，恰好将正数n转换成二进制的时候是逆序的，所以不用储存，一边得出n的2进制一边得到反转后的数m。
时间复杂度：O(1)，由于是将32位无符号数反转，所以要执行32次。
空间复杂度：O(1), 占用固定长度内存。

//乘法循环
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int bit = 0, j = 0;
        uint32_t m = 0;
        while(n)
        {
            bit = n % 2;
            m = m * 2 + bit;
            n /= 2;
            j++;
        }
        while(j++ < 32)
            m *= 2;
        return m;
    }
};

//位操作循环
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t m = 0;
        for(int i = 0; i < 32; n >>= 1, i++)
            m = (m << 1) + (n & 1);
        return m;
    }
};

方法二：位运算
与运算&：当两个位都是1的时候，运算结果位真。
或运算| ：当两个位有一个位是1的时候，结果为真。
左移运算<：将数转换为二进制后向左移动相应的位数，新出现的位用0补充。
右移运算>：将数转换为二进制后向右移动相应的位数，新出现的位用0补充。
0x为十六进制表示方式，1个十六进制数含有4个二进制数，所以：
0xFFFFFFFF : 1111 1111 1111 1111 1111 1111 1111 1111.
0xFFFF0000 : 1111 1111 1111 1111 0000 0000 0000 0000.
0xFF00FF00 : 1111 1111 0000 0000 1111 1111 0000 0000.
ox00FF00FF : 0000 0000 1111 1111 0000 0000 1111 1111.
0xF0F0F0F0 : 1111 0000 1111 0000 1111 0000 1111 0000.
0x0F0F0F0F : 0000 1111 0000 1111 0000 1111 0000 1111.
0xCCCCCCCC : 1100 1100 1100 1100 1100 1100 1100 1100.
0x33333333 : 0011 0011 0011 0011 0011 0011 0011 0011.
0xAAAAAAAA : 1010 1010 1010 1010 1010 1010 1010 1010.
0x55555555 : 0101 0101 0101 0101 0101 0101 0101 0101.
要将32位二进制逆序，可以分为5步来操作，分别是16位交换、8位交换、4位交换、2位交换、1位交换。
时间复杂度：O(1),执行固定次数指令。
空间复杂度：O(1),使用固定长度内存。

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