191. Number of 1 Bits

Leetcode Bit Manipulation

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)$ ：

LeetCode191

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

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