标签: 位运算
难度: Easy
对整数的二进制表示取反（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 < 231注意：本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同
运行时间: 20 ms
内存: 0.0 MB
class Solution:
def findComplement(self, num: int) -> int:
return ((1 << (len(bin(num)) - 2)) - 1) ^ num
这个题解的思路是利用异或运算的性质来求补数。具体来说，先计算出一个和 num 二进制位数相同的掩码，掩码的所有位都是 1，然后将掩码和 num 进行异或运算，得到的结果就是 num 的补数。计算掩码的方法是将 1 左移 num 的二进制位数减 1 位，然后再减 1。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def findComplement(self, num: int) -> int:
# 计算 num 的二进制位数减 1
num_bits = len(bin(num)) - 2
# 计算掩码，掩码的所有位都是 1
mask = (1 << num_bits) - 1
# 将掩码和 num 进行异或运算，得到 num 的补数
complement = mask ^ num
return complement
使用异或运算来求补数可以更加高效且简洁。在二进制中，异或运算的性质是：任何数和1进行异或运算都会得到该数的反转（0变1，1变0），任何数和0进行异或运算结果不变。因此，通过构造一个所有位都是1的掩码，并与原数进行异或，可以直接得到原数的每位取反的结果，这比逐位检查和修改每个二进制位要简单和快速。
掩码是通过计算 num 的二进制位数，然后生成一个长度相同且每一位都是1的二进制数字来确保与 num 对应。具体操作是首先获取 num 的二进制表示的长度（去除前缀'0b'），然后将数字1左移这么多位（即位数减1位，因为左移N位会得到N+1位），最后通过减1将所有高位的0变成1，确保掩码长度和 num 的位数相同。
操作`(1 << num_bits) - 1`中，`1 << num_bits`是将数字1左移num_bits位，左移操作会在右侧补0，因此生成了一个如'1000...000'这样的数字，其中0的个数为num_bits。接着，将这个结果减1，变为'0111...111'，即所有的0都转换成了1，长度为num_bits的掩码，完全由1组成。这样的掩码用来与原数进行异或操作，可以实现对原数每一位的取反。
对于最大的 32 位整数，这种方法依然适用。最大的 32 位整数是 4294967295 (即二进制的'11111111111111111111111111111111')，它的补数结果为0，因为所有位已经是1，异或后变为0。在这种方法中，因为Python的整数类型是动态大小的，所以没有溢出的风险。掩码计算和异或操作都可以在不受固定位数限制的情况下正常进行。