191. Number of 1 Bits.md

title	toc	date	tags	top
191. Number of 1 Bits	false	2017-10-30	Leetcode Bit Manipulation	191

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:

Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011 

Example 2:

Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000

分析

基本的位操作。将整数右移$i$位，后与1按位与(&)，即可得到整数的二进制表示的第$i$位数字。

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++, n >>>= 1)
        count += n & 1;
    return count;
}

也可以将1左移，与整数按位与(&)，得到整数的二进制表示的第$i$位数字，

public int hammingWeight(int n) {
    int count = 0, mask = 1;
    for (int i = 0; i < 32; i++, mask <<= 1)
        if ((n & mask) != 0) count++;
    return count;
}

但是，真的需要一一比对这32位数字吗？例如1，有效位数是1，有必要检查所有数字吗？当然不需要。我们可以在将$n$右移的同时，检测$n$是不是等于0，即检测还有没有有效位。注意右移符号必须是>>>(无符号右移)，而不是>>(有符号右移)。否则当$n$是负数的时候，会产生错误。

public int hammingWeight(int n) {
    int res = 0;
    while (n != 0) {
        res += n & 1;
        n >>>= 1;
    }
    return res;
}

那么还有没有其他更快的方法呢？比如说8，其二进制表示是1000，第1、2种方法需要32次循环，第3种方法需要4次循环，有没有可能只要1次？答案当然是肯定的。该方法需要用到一个技巧：$n$和比它小1的数($n-1$)的按位与($n & (n-1)$)把$n$的最低有效位反转为0，而其他表示不变。所以只要连续做按位与（连续把最低有效位变为0），直到最后结果为0，结束循环，循环的次数就是数字的二进制表示中1的数量。

先来看一个例子，演示$n & (n-1)$：

由于$n$的最低1, 永远在$n-1$种对应0。所以按位与操作才能将最低1转化为0.

public int hammingWeight(int n) {
    int res = 0;
    while (n != 0) {
        n &= n-1;
        res++;
    }
    return res;
}