描述 Description

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.

Example

Given 32, return 1

Given 5, return 2

Given 1023, return 9

Challenge

If the integer is n bits with m 1 bits. Can you do it in O\(m\) time?

[Number of 1 Bits]

分析 Analysis

方法1：移位计数法

循环右移，判断最低位是否为1，是则+1。运算次数与输入n最高位1的位置有关，最多循环32次。

方法2：快速法（lz推荐）

此算法来源于上面提到的 “快速判断一个数是否是2的幂次方”，n&(n-1)可以用于判断一个数的二进制是否只有一个1，而n=n&(n-1) 能移除掉n的二进制中最右边的1的性质，循环移除，直到将1全部移除，这种方法将问题的复杂度降低到只和1的个数有关系，即其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0。

与其等价的另一个快速法：n -= n &(~n + 1)，每次进行这个操作时，也是移除最右侧1的过程。

Note: n &(~n + 1) 这个是经典的得到n中最右侧1的操作。如n = 01000100，则n &(~n + 1) = 00000100。

方法3：平行算法（lz推荐，测试比快速法快）

类似归并过程，组与组之间的数量合并成一个大组，进行下一步归并。

速度不一定最快，但是想法绝对巧妙。思路是先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

lz多解释一下：

n = (n &0x55555555) + ((n >>1) &0x55555555)的结果描述了每两个bit成一组1的数量分布。

以n = -1 即 (1111 1111 1111 1111 1111 1111 1111 1111)为例，n >>1后再与n相加时，每隔一位是没用的，不应该算的，所以每两位一组时要使用01（0x55555555就是(0101 0101 0101....)）来屏蔽，其结果为 (1010 1010 1010 1010 1010 1010 1010 1010)，可以看到每两个 bit成一组1的数量为(10)即2个。

n = (n &0x33333333) + ((n >>2) &0x33333333) ; 以n = -1 即上一步结束后 (1010 1010 1010 1010 1010 1010 1010 1010)，n >>2后再与n相加时，每隔2位是没用的，不应该算的，所以每2位一组时需要使用0011（0x33333333就是(0011 0011 0011....)）来屏蔽，其结果为 (0011)，可以看到每两个 bit成一组1的数量为(10)即2个。

那么n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 就是使用00001111 = 0x0f来屏蔽的。

同理n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 的结果分别描述了每2， 4， 8， 16个bit成一组1的数量分布。

不过为了不重复相加，要设计好几个常数，这点太麻烦了。

其它方法

还有查表法，完美法，位标志法，指令法，MIT hackmem算法等等。[Hacker's Delight]

拓展问题

给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A 和B 的二进制表示中有多少位是不同的？

分为两步，(1)将A和B异或得到C，即C=A^B，(2)计算C的二进制中有多少个1。

代码 Code

方法1

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

方法2

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

方法3

int hammingWeight(uint32_t n){
    n = (n & 0x55555555) + (n >>  1 & 0x55555555); // put count of each  2 bits into those  2 bits 
    n = (n & 0x33333333) + (n >>  2 & 0x33333333); // put count of each  4 bits into those  4 bits 
    n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F); // put count of each  8 bits into those  8 bits 
    n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits 
    n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits 
    return n;
}

位1的个数Number of 1 Bits [**]