位1的个数

发表于

题目

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

1
2
3
public int hammingWeight(int n) {

}

解题

  1. 解法一：通过位运算，逐位对比。任意数与0000 0000 0000 0000 0000 0000 0000 0001对比，都可以让我们知道该数的最低位是否包含1，然后在左移一位，进行下一位的比较，最终得出结果。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public int hammingWeight(int n) {
        int sum = 1;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((sum & n) != 0) {
                count++;
            }
            sum <<= 1;
        }
        return count;
    }

  2. 解法二：通过n和(n-1)的与集，可以把n的最后一个1的值置为0的逻辑，我们进行逐个置零，当最后n变成零则结束，置零的次数为1的个数。

    1
    2
    3
    4
    5
    6
    7
    8
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
       			n &= (n-1);
       			count ++;
        }
        return count;
    }

总结

位运算确实很负责，只能通过多练多记的方式来让自己艰难的掌握了。