[LC]191.位1的个数

题目

分析

逐位数

这题比较简单，直接看代码

class Solution {
public:
    int hammingWeight(int n) {
        size_t hmw = 0;
        for (size_t i = 0; i != sizeof(n) * 8 && n > 0; ++i, n >>= 1)
            if (n & 1) hmw += 1;
        return hmw;
    }
};

时间复杂度：$O(logn).$

空间复杂度：$O(1).$

优化

有两种优化方式

1. $n & (n - 1)$. 通过这个式子，可以将$n$的最低的1置0.

   证明: 对于任意$n = a_la_{l-1}…a_k100…00,n-1=a_la_{l-1}…a_k000…00$，

   则$n&(n-1) = a_la_{l-1}…a{k}000…00$.即最低的1置0.

2. $n&(-n)$.通过这个式子，可以取得$n$的最低的1的值.

   证明：对于任意$n=a_la_{l-1}…a_k100…00,$

   $-n = \overline{a_la_{l-1}…a_k}011…11 + 1 $

   ​ $= \overline{a_la_{l-1}…a_k}100…00$

   所以$n&(-n)$等于$n$的最低的1的值.

通过上面两个式子，我们可以对算法进行优化，使得我们算法循环的次数严格的等于$n$中1的个数。

代码

// 优化方式1
class Solution {
public:
    int hammingWeight(int n) {
        size_t hmw = 0;
        while (n > 0)
        {
            ++hmw;
            n = (n & (n - 1));
        }
        return hmw;
    }
};
// 优化方式2
class Solution {
public:
    int hammingWeight(int n) {
        size_t hmw = 0;
        while (n > 0)
        {
            ++hmw;
            n -= (n & (-n));
        }
        return hmw;
    }
};

时间复杂度：$O(logn).$

空间复杂度：$O(1).$