Number of 1 Bits — Brian Kernighan
Sanjeev SharmaAdvertisement
Problem
Return the number of set bits (1s) in the binary representation of a 32-bit unsigned integer.
Solutions
Python — Brian Kernighan
class Solution:
def hammingWeight(self, n: int) -> int:
count=0
while n: n&=n-1; count+=1
return count
Python — Built-in
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n).count('1')
C
int hammingWeight(uint32_t n) {
int c=0; while(n){n&=n-1;c++;} return c;
}
C++
class Solution {
public:
int hammingWeight(uint32_t n){ return __builtin_popcount(n); }
};
Java
class Solution {
public int hammingWeight(int n){ return Integer.bitCount(n); }
}
Complexity
- Time: O(k) where k = number of set bits (Brian Kernighan)
- Time: O(1) with hardware popcount
Advertisement
