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
def hammingWeight(self, n): """ :type n: int :rtype: int """ c = 0 while n: n &= n - 1 c += 1 return c
second one recursively:
def hammingWeight(self, n, count=0): return self.hammingWeight(n & n-1, count+1) if n!=0 else count
Is it allowed to use built-in function in the interview ?
The function makes the problem too easy.
@munkhjargal As I explained in 2. It does cut the last digit 1 in the binary.
@AmazonMedic I assume not. But from problem solving orientated, that's a solution.
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
n and n-1, compared with
n-1 does have one bit-place difference which makes a
n-1, and with counting recursively, we get all
1 canceled, and return result.
@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))
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.