476. 数字的补数

https://leetcode-cn.com/problems/number-complement/

解法一：

用二进制11111…的十进制减去num即可,关键是求出num有几位.

class Solution:
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        digits = 0
        tmp = num
        while tmp > 0:
            digits += 1
            tmp >>= 1
        return 2**digits - 1 - num

解法二

num的最高为1为从右到左第i位（从0开始），则有：2^i^ <= num < 2^i+1^

又由于1 <= num < 2^31^，因此0 <= i < 31，因此看是否有num >= 2^i^ ，最多用30次比较就可以找到num的最高位1

之后构造num的补码mask=2^i+1^ -1，用mask与num异或即可（py中异或是二进制位运算）

class Solution:
    def findComplement(self, num: int) -> int:
        height = 0	#最高位1的位置
        for i in range(31):
            if num >= 1 << i:
                height = i
        mask = (1 << (height+1)) - 1
        return num ^ mask