# Number of 1 Bits

• The Second Method here should be attributed to Brian Kernighan, since he gave the same.

• According to https://graphics.stanford.edu/..., the earliest publication of the 2nd method is due to Peter Wegner (from CACM 3 [1960], p.322). Also discovered independently by Derrick Lehmer and published in 1964.

The Control Data 6000/7000 series machines (with their 60-bit words and 1s-complement arithmetic) had an instruction to count bits set that they called "population count."

• In Python it could be pretty straightforward (still not so efficient) one-liner: bin(n).count('1')

• Some in Java here. return Integer.bitCount(n) could work.

• 'Same'... Sry about that

• One of the testcases is 2147483648 which is out of int range. How is this being passed to the function that accepts an "int" parameter?

• the number is an unsigned int,right?do{
if(n%2==1)
count++;
n=n/2;
}while(n!=0);

this kind of method is wrong? when running the code ,one of the testcases is 2147483648,why?

• C++ code as below:

class Solution {
public:
int hammingWeight(uint32_t n) {
int cou = 0;
while(n) {
if (n & 1) ++cou;
n >>= 1;
}
return cou;
}
};

The run time is logn, and the space cost only 1.

• For case 315,

input: None
output: 0
expected output: 1

what is None in JS/Java? I try both lang without undefined and null, but the same error exists

• My solution:

return Integer.bitCount(n ^ 0);

was accepted

• A simple
return Integer.bitCount(n);
was also accepted as WTYJack said.

• This post is deleted!

• How is this constant time complexity? Wouldn't it be O(n)?

• There is an even easier bitwise trick which is constant time:
int hammingWeight(uint32_t n)
{
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return (n);
}

• my Python solution:
x = 0
for i in list(bin(n))[2:]:
x += i
return x

• class Solution {
public:
int hammingWeight(uint32_t n) {
int i=0;
while (n)
{
n &= (n-1);
i++;
}
return i;
}
};

• class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
x = 0
while(n>0):
x+=1
n&=n-1
return x

• Approach #2 dramatically reduces the readability while does no good to space and runtime complexity.

• @Eroica I agree about the readability, but the improvement on runtime could be noticed if this function would be applied to lots of integers with only a few bits set. It`s a specific case, but maybe worth mentioning in an interview.

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