191.md

【中规中矩】191. 位1的个数 （两种解法）

解题思路

解法1：暴力循环移位并且bit and获取每位上的数字，如果为1则累计总数即可。O(N)

解法2: 利用n&(n -1)可以清除最低位1的性质，循环每次清除一个位，直到n为0返回循环次数即可。O(lgN)

代码

class Solution1 {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        for (int i = 31; i >= 0; i--) {
            count += (n >> i) & (0x1);
        }

        return count;
    }
};

class Solution2 {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }

        return count;
    }
};

class Solution1:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for i in range(31, -1, -1):
            count += (n >> i) & (0x1)

        return count

class Solution2:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while (n != 0):
            n &= (n - 1)
            count += 1
        return count

点我赞赏作者

github 题解