476. Number Complement

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

Description

The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation.

For example, the integer 5 is "101" in binary; its complement is "010", which is the integer 2.

Given an integer num, return its complement.

Answer

class Solution:
    def findComplement(self, num: int) -> int:
        bit_len = num.bit_length()
        mask = (1 << bit_len) - 1
        return num ^ mask

Solution

This problem is a bit manipulation that involves flipping the bits. Whenever this happens, the first thing that comes to mind should be XOR because the XOR logic is equivalent to even parity.

Then, all we need is a bitmask consisting of all 1’s that is the length of the binary representation of num. We can achieve this by shifting 1 to the left by the length of the binary representation of num then subtracting 1.

Once we have our bitmask, we can simply XOR with our original number and return the result.