**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
```