476. 数字的补数

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

考点

  • 异或技巧
  • 掩码技巧
  • 移位技巧

题解

1
2
3
4
5
6
7
8
9
10
class Solution {
	public:
		int findComplement(int num) {
			int mask = 0;
			for (int i = num; i; i = i >> 1) {
				mask = (mask << 1) | 1;
			}
			return num ^ mask;
		}
};

时间复杂度：\(O\left( \log num \right)\)

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

思路

某一个比特位要反转，直接令其异或1即可

假设整数去掉前导零后的真实长度为n，我们做一个长度也为n的全1掩码，然后让掩码与整数异或运算即可

0000 0101 ^ 0000 0111 = 0000 0010