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.
給定一個unsigned integer數(shù)，返回bit值為1的個數(shù)

算法分析

方法一

將給定數(shù)值與1做“與”運算，即可得到結(jié)果

Java代碼

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        int mask = 1;
        for (int i = 0; i < 32; i ++) {
            if ((n & mask) != 0) {
                count ++;
            }
            mask = mask << 1;
        }
        return count;
    }
}

方法二

如圖1所示，n & (n - 1)運算

Paste_Image.png

Java代碼

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

參考

LeetCode