Leetcode

476. Number Complement

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:

1
2
3
4
> 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:

1
2
3
4
> 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.
>

Method1:

阶段1

1 ^ 1 = 0

0 ^ 1 = 1

==> 11111 ^ 10101 = 01010 —> The answer

==> Target: Establish 1111111 (len == num的二进制数字）

阶段2

n = len(bin(num))-2 设定num的二进制长度n 为 6

6个1: $111111 —> 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5= 2^6 -1$

1
2
3
4
5
class Solution:
	def findComplement(self, num):
        n = len(bin(num))-2
        temp = 2**n -1
        return num ^ temp

Method2:

Step1. 翻转, Target

设定为5

十进制 2进制
5 …000101
~5 …111010 010部分为ans
Target …111000 Target^ ~num为ans

Step2

Target: …..111000

1
2
3
mask = ~0
for i in range(len(bin(num))-2):
    mask << 1

Solution

1
2
3
4
5
6
7
8
9
class Solution:
	def findComplement(self, num):
		# Find mask
        mask = ~0
        for i in range(len(bin(num))-2):
            mask <<= 1
            
		# Get ans
        return ~num ^ mask