Problem statement

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

Solution

There is very smart solution, where we spread the highest 1-bit onto all the lower bits.

Complexity

It is just 5 operations we need to do here.

Code

class Solution(object):
    def findComplement(self, num):
        mask = num
        mask |= mask >> 1
        mask |= mask >> 2
        mask |= mask >> 4
        mask |= mask >> 8
        mask |= mask >> 16
        return num ^ mask

Remark

Another solutions:

We can just find length of number k and subtract number from 2^k-1.

We can also use x & (x-1) trick, and delete ones from the end one by one until we reach power of two (we need to make step if x & (x-1) is not equal to zero). When we reached power of two s, we evaluate (2s+1) ^ num. Complexity is O(q), where q is number of non-zero bits.