剑指 Offer 15. 二进制中1的个数

剑指 Offer 15. 二进制中1的个数

• 解题思路
• 代码

解题思路

第一种常规解法：不断右移n。

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

第二种方法（最优的）：巧用 n&(n−1)
每次执行n&(n−1)都会 消去数字 n 最右边的 1。只要执行一次，res+1即可。

代码

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