190. 颠倒二进制位

发表于 分类于 阅读次数： Waline： 本文字数： 253 阅读时长 ≈ 1 分钟

考点

  • 位运算与分治法的综合
  • 掩码技巧
  • 移位技巧

题解

同下

思路

逐位移动

通过循环，每次新变量向左移位后接收n的低位，自然n的低位变成新变量的高位了

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 0; i < 32; n = n >> 1, i++){
            ans <<= 1;
            ans |= n & 1;
        }
        return ans;
    }
};

时间复杂度：\(O\left( k \right)\)，这里\(k\)等于位数32

空间复杂度：\(O\left( 1 \right)\)

分治

参考191. 位1的个数中的分治法

将二进制整串均分成左右两子串，每个子串同样递归地执行翻转操作，最后将左右子串交换位置完成翻转

1
2
3
4
5
6
7
8
9
10
11
class Solution {
	public:
		uint32_t reverseBits(uint32_t n) {
			n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
			n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
			n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
			n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
			n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
			return n;
		}
};

时间复杂度：\(O\left( \log C \right)\)，这里\(C\)等于位数32

空间复杂度：\(O\left( 1 \right)\)