191.位1的个数

题目:191.位1的个数

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为 汉明重量）。

• 示例 1：

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

• 示例 2：

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

• 示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

• 提示：

1 <= n <= 2^31 - 1

• 进阶：

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

思路

可以通过逐位检查来实现这个函数，逐步提取每一位，判断是否为 1，然后统计总数。以下是一个具体实现方案：

1. 通过 n & 1 可以判断 n 的最低位是否为 1。
2. 每次右移 n 一位，即 n >>= 1，逐步检查每一位。
3. 当 n 为 0 时，停止循环，输出结果。

• 时间复杂度:O(1)
• 空间复杂度:O(1)

代码

public int hammingWeight(int n) {
    // 用于记录1的数量
    int count = 0;
    while (n != 0) {
        // 每次判断最低位是否为1
        if ((n & 1) == 1) {
            count++;
        }
        // 右移一位，继续检查下一位
        n = n >> 1;
    }
    // 返回1的总个数
    return count;
}