05 August 2008
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Example 1:
1
2
3
Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011
Example 2:
1
2
3
Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000
这道题是给一个无符号的整数，将之转换成二进制的形式后，总共有多少个1，这样 1的个数也叫做Hamming Weight，就是在一串字符中有多少个非0符号，在信息论，编译原理和密码学中Hamming Weight应用广泛。
我们可以从左到右循环，每次把n向右移动一位，把n和1进行&操作，判断结果是否为1，然后数个数，这种做法会超时。
用n & (n - 1)的办法，如果将一个整数减去1，那么都是把最右边那个1变成0，如果这个1右边还有0，所有的0全部变成1，但是这个1左边数字均保持不变；把这个整数和它减去1的结果进行&的话，就可以得到最右边的1。比如110，减去1得101，二者&操作后得100，消去了最右边的1，依次类推。
Time： O(1)； Space： O(1)；
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int result = 0;
while (n != 0) {
result++;
n = n & (n - 1); // 每轮消掉一个1，看总共几轮就消掉几个1
}
return result;
}
}