LeetCode 476. Number Complement

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

I love bit manipulation problems. Some of the tricks are just like magic. XOR is one of those magic operators that when used properly can yield surprisingly concise solutions. A couple of quick usages of XOR:

• XOR a number with itself odd number of times the result is number itself.
• XOR a number even number of times with itself, the result is 0.
• XOR with 0 is always the number itself.
• XOR a number say (5=110) with (111) will flip the bits and yield (1=001).

The complement of a number is exactly a direct application of the last bullet point. We just need to XOR the number with the maximum number that can be formed using the same number of bits. So the task is just to find the number of bits the input number has and construct that number in a decimal form that will be XORed with the input number to get the complement. Getting the binary representation of a number is a fairly standard procedure that everyone should know.

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        binmax = 0
        i = 0
        ans = num
        while num//2 !=0:
            binmax += 2**i
            i += 1
            num //=2
        binmax += 2**i
        return ans ^ binmax