# Python solution with detailed explanation

• Solution

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

Algorithm

• Find the index of the first set bit O(32). Simply XOR the input until that bit: O(32).
``````class Solution(object):
def find_last_set_bit(self, num):
last_set_bit, mask = 0, 1
for i in range(32):
if (mask << i) & num:
last_set_bit = i
return last_set_bit

def findComplement(self, num):
"""
:type num: int
:rtype: int
"""
last_set_bit, mask = self.find_last_set_bit(num), 1
for i in range(last_set_bit+1):
num = num ^ (mask << i)
return num
``````
• Find the power of 2 number larger than num. Then i-1 will unset the last set bit and set all bits to its right to 1. Then just XOR with this number.
``````class Solution(object):
def findComplement(self, num):
"""
:type num: int
:rtype: int
"""
i = 1
while i <= num:
i = i << 1
return (i-1)^num
``````

• @gabbu We can make use of "bit_length()" function of python to eliminate some looping.

We can do something like this

``````class Solution(object):
def findComplement(self, num):
"""
:type num: int
:rtype: int
"""
msb = num.bit_length()
return (2**msb-1) ^ num
``````

This uses similar approach as yours just by avoiding loops.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.