0476. Number Complement

# 476. Number Complement#

## 题目 #

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:

``````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:

``````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.
``````

## 代码 #

``````
package leetcode

// 解法一
func findComplement(num int) int {
xx := ^0 // ^0 = 1111111111111111111111
for xx&num > 0 {
xx <<= 1 // 构造出来的 xx = 1111111…000000，0 的个数就是 num 的长度
}
return ^xx ^ num // xx ^ num，结果是前面的 0 全是 1 的num，再取反即是答案
}

// 解法二
func findComplement1(num int) int {
temp := 1
for temp <= num {
temp <<= 1 // 构造出来的 temp = 00000……10000，末尾 0 的个数是 num 的长度
}
return (temp - 1) ^ num // temp - 1 即是前面都是 0，num 长度的末尾都是 1 的数，再异或 num 即是最终结果
}

``````

Apr 8, 2023