LeetCode 191. 位1的个数

Categories:

题目描述
思路分析
1. 解法一：n & (n-1) 消去最低位（推荐）
2. 解法二：逐位检查
相似题目

题目描述

✅ 191. 位1的个数

思路分析

解法一：n & (n-1) 消去最低位（推荐）

核心思路：

n & (n-1) 可以将 n 的二进制中最低位的 1 消去。

例如：n = 12（1100），n-1 = 11（1011），n & (n-1) = 8（1000），消去了最低位的 1。

循环执行此操作，每次消去一个 1，直到 n 变为 0，循环次数即为 1 的个数。

此方法时间复杂度取决于 1 的个数 k，当 1 较少时效率更高。

复杂度分析：

时间复杂度：O(k)，其中 k 表示 n 的二进制中 1 的个数，最坏情况 O(32)

空间复杂度：O(1)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        // 每次消去最低位的 1，直到 n 为 0
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

func hammingWeight(n uint32) int {
    count := 0
    // 每次消去最低位的 1，直到 n 为 0
    for n != 0 {
        n = n & (n - 1)
        count++
    }
    return count
}

解法二：逐位检查

核心思路：

每次检查 n 的最低位是否为 1（使用 n & 1）。

然后对 n 进行无符号右移（n >>> 1），将下一位移到最低位。

循环 32 次，统计所有为 1 的位。

此方法时间复杂度固定为 O(32)，与 1 的个数无关。

复杂度分析：

时间复杂度：O(32)，即 O(1)，固定循环 32 次

空间复杂度：O(1)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        // 固定循环 32 次，逐位检查是否为 1
        for (int i = 0; i < 32; i++) {
            // 检查当前最低位是否为 1
            if ((n & 1) == 1) {
                count++;
            }
            // 无符号右移，避免符号位扩展问题
            n >>>= 1;
        }
        return count;
    }
}

func hammingWeight(n uint32) int {
    count := 0
    // 固定循环 32 次，逐位检查是否为 1
    for i := 0; i < 32; i++ {
        // 检查当前最低位是否为 1
        if n&1 == 1 {
            count++
        }
        // 右移一位，检查下一位
        n >>= 1
    }
    return count
}

相似题目

题目	难度	考察点
231. 2 的幂	简单	位运算
190. 颠倒二进制位	简单	位运算
338. 比特位计数	简单	位运算、动态规划
461. 汉明距离	简单	位运算
477. 汉明距离总和	中等	位运算
693. 交替位二进制数	简单	位运算
762. 素数排列	简单	位运算、数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/15862521