浅谈 颠倒二进制位 问题

颠倒二进制位

颠倒给定的 32 位无符号整数 的二进制位。

思路：

1. 从最低位遍历 n，并将 n 右移一位。
2. 将 n 的最低位依次变为最高，第二高位，……
3. 直到 n 变为 0 则结束。
4. 返回倒叙。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        auto i = 0;
        while(n) {
            res |= (n & 1) << (31 - i);			// 只能先求与再移位, 将 n 的最低位添到 res 最高位后
            ++i;								// 因为求与后的结果会被放到临时分配的内存中，不会影响 n 的值
            n >>= 1;
        }
        return res;
    }
};

时间复杂度：O(log(n))
空间复杂度：O(1)