LeetCode476 Number Complement

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

  1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
  2. You could assume no leading zero bit in the integer’s binary representation.

样例

Example 1:

1
2
3
4
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits),
and its complement is 010. So you need to output 2.

Example 2:

1
2
3
4
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits),
and its complement is 0. So you need to output 0.

思路

求一个32-bit正数各二进制位取反后的数。

位运算的简单操作。通过移位运算符取得num第i位上的数,再用异或操作取反(与1进行异或),最后用运算加到ans的第i位上即可。

另一个思路是,用二进制位数和num一样且各位都为1的数与num异或即为答案。

比如

1
2
3
4
  10101 <- num
^ 11111 <- 二进制全为1
-------
01010

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int findComplement(int num) {
int ans = 0;
for (int i = 0; num; num >>= 1, ++i) {
ans |= (((num & 1) ^ 1) << i);
}
return ans;
}
};
1
2
3
4
5
6
7
8
class Solution {
public:
int findComplement(int num) {
unsigned int ans = 1;
while (ans <= num) ans <<= 1;
return (ans - 1) ^ num;
}
};
分享到 评论