【力扣】191.位 1 的个数

191.位 1 的个数

题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11

输出：3

解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128

输出：1

解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645

输出：30

解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 231 - 1

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

解题方法

• C 循环检查

int hammingWeight(int n) {
    int cnt = 0;
    unsigned int m = 0x1; // 必须定义为“无符号”型
    for (int i = 0; i < 32; i++) {
        if (n & (m << i)) {
            cnt++;
        }
    }
    return cnt;
}

复杂度分析：

时间复杂度为 O(k)，其中 k 是 int 型的二进制位数，k = 32。

空间复杂度为 O(1)。