[数据结构与算法]LeetCode 476 数字的补数

LeetCode 476 数字的补数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-complement/

博主Github：https://github.com/GDUT-Rp/LeetCode

题目：

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。
给你一个整数 num ，输出它的补数。

示例 1:

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2:

输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

提示：

1 <= num < $2^{31}$

解题思路：

方法一：找二进制规律然后相减

直观想法

原数字num + 其补数 + 1 = $2^n$ (刚好比起>=的一个数)

C++

Golang

func findComplement(num int) int {
    two_pow := 1
    for i:=0; i<=32; i++ {
        if two_pow - 1 >= num {
            return two_pow - num - 1
        } 
        two_pow = two_pow << 1
    }
    return 0
}

Python

class Solution:
    def __init__(self):
        self.two_pows = [2 ** i - 1 for i in range(32)]

    def findComplement(self, num: int) -> int:
        for elem in self.two_pows:
            if elem >= num:
                return elem - num

复杂度分析

时间复杂度：$O(n)$

方法二：异或运算符

找到最大的 $2^n$，然后进行异或运算符运算即可以取补数。

C++

class Solution {
public:
    int findComplement(int num) {
        int temp = num, c = 0;
        while (temp > 0) {
            temp >>= 1;
            c = (c << 1) + 1;
        }
        return num ^ c;
    }
};

Go

func findComplement(num int) int {
    temp := num
    c := 0
    for temp > 0 {
        temp >>= 1
        c = (c << 1) + 1
    }
    return num ^ c
}

Python

class Solution:
    def findComplement(self, num: int) -> int:
        temp = num
        c = 0
        while temp > 0:
            temp >>= 1
            c = (c << 1) + 1
        return num ^ c