191. Number of 1 Bits
- Total Accepted: 119474
- Total Submissions: 312895
- Difficulty: Easy
- Contributors: Admin
Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.
Code
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
sum = 0
for i in xrange(32):
sum += (n >> i) & 1
return sum
Idea
Classic bit operation to count 1.
Another way to count 1 is to do n = n & (n-1) until n is equal to 0:
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
count = 0
while n:
n = n & (n-1)
count += 1
return count
Reference: https://discuss.leetcode.com/topic/20120/c-solution-n-n-1