Python 4 ways


  • 18
    1. Flip bit by bit.
    class Solution(object):
        def findComplement(self, num):
            i = 1
            while num >= i:
                num ^= i
                i <<= 1
            return num
    
    1. Find the bit length (say L) and flip num by num ^ 11...1 (L ones).
        def findComplement(self, num):
            return num ^ ((1<<num.bit_length())-1)
    
    1. Again find the bit length first.
        def findComplement(self, num):
            return num ^ ((1 << len(bin(num)) - 2) - 1)
    
    def findComplement(self, num):
            return num ^ ((2<<int(math.log(num, 2)))-1)
    

    We can also flip num first (including the leading zeros) using ~num and then get the last L bits by & 11...1 (L ones).

    For example,

        def findComplement(self, num):
            return ~num & ((1<<num.bit_length())-1)
    

  • 0
    A

    His website has a great analysis into this algorithm:
    http://liqichen.com/daily-leetcode476-number-complement/


Log in to reply
 

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