LeetCode偶尔一题 —— 476. 数字的补数

题目描述📄

给定一个正整数,输出它的补数。补数是对该数的二进制表示取反。

注意:
给定的整数保证在32位带符号整数的范围内。
你可以假定二进制数不包含前导零位。

题目剖析🧐

我们注意到:

  • 给定的整数在 32 位带符号整数的范围内,也就是说给定的 num0 < num <= 2^31
  • 二进制数不包含 前导零位,也就是说不用考补数不用考虑二进制的 符号位
  • 取某一位的补数其实就是那一位跟 1 进行 异或运算

示例代码🌰

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number} num
* @return {number}
*/
var findComplement = function(num) {
let tmp = num, i = 0
while (tmp) {
num ^= 1 << i
tmp >>= 1
i++
}
return num
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)