PROBLEM

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

难度 简单

MY ANSWER

逐位判断，时间复杂度O(log n)，空间复杂度O(1)。

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

BETTER SOLUTION

使用n&(n - 1)循环消去最右边的1。

image-20210906131214558

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

SUMMARY

使用n&(n - 1)可消去n最右边的1。