位1的个数

来源Leetcode第191题位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

公式

1.计算出来的值i的二进制可以按每2个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。
2.计算出来的值i的二进制可以按每4个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。
3.计算出来的值i的二进制可以按每8个二进制位为一组进行分组，各组的十进制表示的就是该组的汉明重量。
4.i * (0x01010101)计算出汉明重量并记录在二进制的高八位，>>24语句则通过右移运算，将汉明重量移到最低八位，最后二进制对应的十进制数就是汉明重量。
算法时间复杂度是O（1）的。

public int hammingWeight(int i) {
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);  //相邻位相加
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  //相邻为以2为单位相加
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);  //相邻为以4为单位相加
i = (i * (0x01010101) >> 24);
return i;
}

循环移位

执行32次，每次与1相与，判断结果后累加

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

位操作

来源官方题解

在二进制表示中，数字 nn 中最低位的 11 总是对应 n - 1n−1 中的 00 。因此，将 nn 和 n - 1n−1 与运算总是能把 nn 中最低位的 11 变成 00 ，并保持其他位不变。

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

Integet类库

1
2
3

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

lowbit公式

lowbit公式： x & ~x
作用是找出数字n中最后一个1出现的位置
例如n = 10。用二进制表示就是1010，而它的负数-10用二进制补码表示则为0110，
取&后得到的结果为10，这就得到了n最后一个1出现的位置对应的数字。
知道lowbit公式后，这个题目就非常简单了。每次通过lowbit公式找到最后一个1对应的数，然后将它减去，直到n为0为止。统计减法操作的次数即可。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ans = 0;
        while(n != 0) {
            ans++;
            n -= lowbit(n);
        }
        return ans;
    }
    
    private int lowbit(int x) {
        return x & -x;
    }
}