二进制中1的个数

Question

对于一个无符号整型变量，求其二进制表示中1的个数。
[题目来源：编程之美]

Note

• 算法一：与0x01位与，右移位。
• 算法二：n & (n-1)。

Extension

• 比较两个数A和B的二进制表示中有多少位是不同的：先异或，然后计算异或结果中1的位数。

Solution

// 解法一：求二进制表示中1的位数：n & (n-1)。
public int countOnes(int num) {
    int count = 0;
    while (num > 0) {
        num &= num - 1;    // key
        count++;
    }
    return count;
}

// 解法二：右移位
public int countOnes(int num) {
    int count = 0;
    while (num > 0) {
        count += num & 0x01;
        num >> 1;
    }
    return count;
}