题目描述：

LeetCode 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

题目大意：

给定一个正整数，输出其补数。补充策略就是按二进制位反转。

注意：

1. 给定正数确保是32位带符号整数。
2. 可以假设整数的二进制表示不包含前导0。

解题思路：

解法I 位运算（异或）

Python代码：

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        mask = (1 << 1 + int(math.log(num, 2))) - 1
        return mask ^ num

解法II 按位取反并累加

Python代码：

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        return int(''.join(str(1 - int(x)) for x in bin(num)[2:]), 2)

 

本文链接：http://bookshadow.com/weblog/2017/01/08/leetcode-number-complement/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码