476. Number Complement

原题网址：https://leetcode.com/problems/number-complement/description/
大意：求一个数的补数，比如，5的二进制是101,1变0,0变1，得到010,010还原十进制就是2，所以输入5，输出2.

本来想用python的~方法，但是有一个问题，5的python3的~5的到的是-6，为啥呢，因为python是32位求补，101的32位取反，得到的是1111 1111 1111 1111 1111 1111 1111 1010这个数的开头是1，说明是一个负数，求他的源码，需要取反加1，又变为0000 0000 0000 0000 0000 0000 0000 0101 + 1 = 0000 0000 0000 0000 0000 0000 0000 0110 为6，再加个负号，就是-6
因此，可以总结出~位取反的计算结论是：~n = -(n+1)
例如本例中，~5 = -(5+1)，即~5 = -6

那就要换个思路，

1. 找到最小的大于原数字的二进制值仅有一位为1的数；
2. 将此数减1；
3. 与原数字按位求异或。

# 476. Number Complement
class Solution:
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        all_ones = 1
        while all_ones <= num:
            all_ones <<= 1
        all_ones -= 1
        return all_ones ^ num

a = Solution()
print (a.findComplement(5))
print(~5)