问题描述
每个非负整数 N 都有其二进制表示，比如 5 可以表示为 101，11 可以表示为 1011。但是注意 0，其前面没有多余的 0。
二进制的补码是指把 1 变成 0，0 变成 1。比如 101 的补码是 010。
给定一个非负整数 N，以 10 为基数，要求将其二进制转换成补码后，返回其表示的整数值。
栗子1：
输入：5
输出：2
5 -> 101，补码 010 -> 2
栗子2：
输入：7
输出：10
7 -> 111，补码 000 -> 0
栗子3：
输入：10
输出：5
10 -> 1010，补码 0101 -> 5
注意： 0 <= N < 10^9
想看英文的戳这里：原题地址
解题思路
常规解法
比较容易想到的解法是逐步将每位进行取反，然后计算转成后二进制的数值。
swift 代码如下：
// 8.47%
func bitwiseComplement(_ N: Int) -> Int {
// 0 需要注意
if (N == 0) {
return 1
}
var result = 0
var count = 0
var tmp = N
// 从后往前，对于每位取反
while tmp != 0 {
// 取出每位
let bit = tmp & 1
// 0->1, 1->0
let complementBit = 1 - bit
// 不断计算数值，由于是从后往前的，需要进行移位。
result |= (complementBit << count)
tmp = tmp >> 1
count += 1
}
return result
}
但是提交之后，只打败了 8.47%，说明这只是一种暴力解法，肯定还有更优解，而不用去直接计算每位的补码。
更优解法
这里需要我们有点计算机基础知识，或者可以通过观察栗子，得到其中的规律。
因为是对每位取反，110 -> 001，101 -> 010，可以总结出它们相加的和一定是 S = 111。对于 4 位的二进制，其和为 S = 1111。
所以只需要计算出 S，S - N 即为结果。
那么 S 如何计算？
我的思路是：如果 N 有 k 位，那么 S = 2 ^ k - 1。如 N 有 3 位，则 S = 7。实际我们不必等到把 k 完全算出来之后，再做 k 次方的操作， 可边算位数边计算结果。当 1位为 1，2 位为 11，3 位为111，即result = (result << 1) | 1。
swift 代码如下：
// 98.36%
func bitwiseComplement3(_ N: Int) -> Int {
if (N == 0) {
return 1
}
var result = 0
var tmp = N
while tmp != 0 {
result = (result << 1) | 1
tmp = tmp >> 1
}
return result - N
}
beat 98.36%。
网上解法
思路类似，就是找 S 的方式不一样。由于 S = 1、3、7、15、...，只需不断遍历，找到 S >= N 的第一个数即可，更加简单。
swift 代码如下：
// 100%
func bitwiseComplement4(_ N: Int) -> Int {
var S = 1
while S < N {
S = (S << 1) | 1
// S = S * 2 + 1
}
return S - N
}
需要注意的是：使用位操作会快很多，beat 100%，但如果用 S = S * 2 + 1，则只有 9.84%。
