[Python] 2 solutions. One naive solution with built-in functions. One trick with bit operation


  • 12
    B

    1.Built in solution with built-in function:

    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count('1')
    

    2.Using bit operation to cancel a 1 in each round

    Think of a number in binary n = XXXXXX1000, n - 1 is XXXXXX0111. n & (n - 1) will be XXXXXX0000 which is just cancel the last 1

    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        c = 0
        while n:
            n &= n - 1
            c += 1
        return c

  • 1
    Y

    The second one is tricky, and is so helpful. Thanks for sharing!


  • 3

    second one recursively:

    def hammingWeight(self, n, count=0):
        return self.hammingWeight(n & n-1, count+1) if n!=0 else count 
    

  • 0
    A

    @BigTailWolf

    Is it allowed to use built-in function in the interview ?
    The function makes the problem too easy.


  • 0
    M

    what does it mean when theres n &= n-1 ?


  • 0
    B

    @munkhjargal As I explained in 2. It does cut the last digit 1 in the binary.


  • 0
    B

    @AmazonMedic I assume not. But from problem solving orientated, that's a solution.


  • 0
    S

    Maybe only saying "It does cut the last digit 1 in the binary" still confusing more or less..
    So at first & bit operator is: 1 if both bits are 1, else 0
    Then consider n and n-1, compared with n,n-1 does have one bit-place difference which makes a 1 in n becoming 0 in n-1, and with counting recursively, we get all 1 canceled, and return result.


  • 0
    S

    @ahendy oh nope dude, you actually change the question's default function variables from def hammingWeight(self, n) to def hammingWeight(self, n, count=0)

    Here is my recursion version:

    def hammingWeight(self, n):
            return 0 if n == 0 else 1 + self.hammingWeight(n&(n-1))
    

Log in to reply
 

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