LeetCode 1009. Complement of Bas

问题描述

每个非负整数 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%。