企业官网建设流程全解析

LeetCode-Book 精讲：位 1 的个数（191. Number of 1 Bits）——逐位判断与n & (n - 1)两种位运算解法剖析

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本文基于本仓库 191. 位1的个数 文档展开，并结合仓库内 Python / Java / C++ 三套源码（lc_191_number_of_1_bits_s1与s2）逐行印证。读完本文，你将掌握汉明重量（Hamming Weight）的两种经典求法——逐位右移计数与n & (n - 1)快速消位法，理解无符号右移在 Java / Python / C++ 中的实现差异，并能在真实运行环境中复现验证。

一、题目背景与核心概念

「位 1 的个数」（LeetCode 191，剑指 Offer 15「二进制中 1 的个数」为同题）要求：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为1的个数。

这个问题在工程与面试中之所以高频出现，是因为它考察两个基础且重要的能力：

1. 位运算基本功：与（&）、或（|）、异或（^）、取反（~）、左移（<<）、右移（>>）的语义与组合运用；
2. 对「无符号数」语义的理解：题目把输入视为无符号整数，因此高位补位的行为必须明确（逻辑右移 vs 算术右移）。

在计算机体系结构中，统计一个二进制串中1的个数被称为汉明重量（Hamming Weight），它也是汉明距离（Hamming Distance，即两个等长串之间不同位的个数）的计算基础，常见于信息论、校验码与数据去重等场景。

下文将完整呈现仓库文档中的两种解法，并给出对应的源码级佐证。

二、位运算预备知识：与运算与右移

方法一依赖两条最基本的位运算性质。设二进制数字为n，则有：

• 若n & 1 = 0，则n二进制最右一位为0；
• 若n & 1 = 1，则n二进制最右一位为1。

也就是说，n & 1的值恰好等于n最低位的取值——它用一条与运算就把「取最低位」这件事完成了，这是逐位计数法的根基。

右移运算则用于「消费」已检查过的低位：

• 逻辑右移（无符号右移）：高位补0；
• 算术右移（有符号右移）：高位补符号位。

由于本题将n视为无符号数，右移必须采用无符号右移 / 逻辑右移，三语言的处理方式在仓库源码中各有体现（详见下文各节）。

三、方法一：逐位判断（循环右移 + 与运算）

3.1 算法原理与流程

根据「n & 1即最低位」的性质，可以设计如下循环：

1. 初始化数量统计变量res = 0；
2. 循环逐位判断：当n = 0时跳出；
   • res += n & 1：若n & 1 = 1，则统计数res加一；
   • n >>= 1：将二进制数字n无符号右移一位；
3. 返回统计数量res。

整个流程等价于：每次只「看」最低位，看完就右移丢弃，直到n变为0。

3.2 三种语言实现与无符号右移的差异

仓库文档与源码中，三语言实现思路完全一致，但右移写法因语言特性而不同：

Python（lc_191_number_of_1_bits_s1.py）：

class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n: res += n & 1 n >>= 1 return res

Python 的整数是任意精度、非负数按位存储，对非负输入使用>>即等价于逻辑右移，因此直接n >>= 1即可，无需区分算术右移与逻辑右移。

Java（lc_191_number_of_1_bits_s1.java）：

public class Solution { public int hammingWeight(int n) { int res = 0; while (n != 0) { res += n & 1; n >>>= 1; } return res; } }

Java 的int是 32 位有符号类型，必须使用无符号右移运算符>>>。若误用带符号右移>>，当最高位为1（即 n 作为有符号数为负数）时高位会补1，循环将无法在n = 0时终止。这正是本题最容易踩的坑，也是源码选择>>>的原因。

C++（lc_191_number_of_1_bits_s1.cpp）：

class Solution { public: int hammingWeight(uint32_t n) { unsigned int res = 0; // c++ 使用无符号数 while (n != 0) { res += n & 1; n >>= 1; } return res; } };

C++ 直接以uint32_t声明参数，用无符号类型本身保证>>是逻辑右移，因此res也相应使用无符号类型承接统计结果，源码中注释「c++ 使用无符号数」点明了这一设计意图。

3.3 运行验证（C++ 驱动示例）

仓库中的 C++ 文件带有可直接运行的main与测试用例（lc_191_number_of_1_bits_s1.cpp）：

int main() { // ======= Test Case ======= uint32_t n = 0b00000000000000000000000000001011; // ====== Driver Code ====== Solution* slt = new Solution(); int res = slt->hammingWeight(n); cout << res << endl; return 0; }

输入0b...1011（十进制 11）的二进制表示含1的个数为 3，程序输出3，与逐位手算一致。其余语言的驱动骨架（Solution实例化 +hammingWeight调用）同样保留在 Python s1 与 Java s1 中，可直接补入测试输入运行。

3.4 复杂度分析

• 时间复杂度 O(log n)：循环内部仅有移位、与、加等基本运算，占用 O(1)；逐位判断需循环log₂n次，其中log₂n代表数字n最高位1所在位数（例如log₂4 = 2、log₂16 = 4）。注意这里与 n 的数值大小相关，而非与1的个数相关。
• 空间复杂度 O(1)：变量res使用常数大小额外空间。

四、方法二：巧用n & (n - 1)消去最右边的 1

方法一的循环次数取决于n的二进制位长；方法二则把循环次数压缩到「1 的个数」，性能由 O(log n) 提升为 O(M)（M 为二进制中 1 的个数）。

4.1 核心位运算性质推导

两个关键运算的作用：

• (n - 1)的作用：二进制数字n最右边的1变成0，此1右边的所有0都变成1。例如n = 0b101100时，n - 1 = 0b101011——最低位的那个1（第 3 位）变为0，其右侧的两个0变为1，更高位不变。
• n & (n - 1)的作用：二进制数字n最右边的1变成0，其余位保持不变。沿用上例：0b101100 & 0b101011 = 0b101000，恰好消去了原数最右边的那个1。

之所以成立，是因为n与n - 1仅在「最右侧1及其右侧部分」上不同，而该1左侧的高位在两数中完全相同，与运算后原样保留。

4.2 算法流程

1. 初始化数量统计变量res；
2. 循环消去最右边的1：当n = 0时跳出；
   • res += 1：统计变量加1；
   • n &= n - 1：消去数字n最右边的1；
3. 返回统计数量res。

每轮循环必然消去一个1，因此总循环次数等于1的个数 M。

4.3 三种语言实现

Python（lc_191_number_of_1_bits_s2.py）：

class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n: res += 1 n &= n - 1 return res

Java（lc_191_number_of_1_bits_s2.java）：

public class Solution { public int hammingWeight(int n) { int res = 0; while (n != 0) { res++; n &= n - 1; } return res; } }

C++（lc_191_number_of_1_bits_s2.cpp）：

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

该方法不依赖右移方向，三种语言中n & n - 1的语义完全一致，因此实现高度统一；C++ 版本同样以uint32_t声明入参，驱动用例与 s1 相同（输入0b...1011，输出3）。

4.4 复杂度分析

• 时间复杂度 O(M)：n & (n - 1)操作仅有减法和与运算，占用 O(1)；设 M 为二进制数字n中1的个数，则每轮消去一个1，共需循环 M 次，占用 O(M)。
• 空间复杂度 O(1)：变量res使用常数大小额外空间。

当n中1很少（如稀疏的掩码值）时，方法二优势显著；即使最坏情况（如0xFFFFFFFF，M = 32），循环次数也恒定为 32，与位长相当，整体上方法二通常更优。

五、两种方法对比小结

两种解法均已收录于 docs/191. 位1的个数.md 的「方法一：逐位判断」与「方法二：巧用n & (n - 1)」两节，仓库内代码目录lc_191_number_of_1_bits（Java、C++）与lc_191_number_of_1_bits_s1/s2.py（Python）一一对应，命名中的_s1/_s2即解法序号，方便对照查阅。

六、位运算专题在仓库中的延伸

理解本题后，可以沿着仓库的位运算专题继续深挖，同类思想在多题中复用：

• 136. 只出现一次的数字：利用异或（^）的「自反性」在 O(n) 时间内找出唯一出现一次的数字，对应源码 lc_136_single_number.py；
• 371. 两整数之和：在不使用加减法的约束下，用「与运算 + 左移」求进位、用异或求无进位和，递归迭代完成加法；
• 231. 2 的幂：判断一个数是否为 2 的幂，n & (n - 1) == 0正是最优雅的位运算判据，与本篇方法二共用同一核心技巧；
• 同题复现：剑指 Offer 15. 二进制中 1 的个数 与本题解法完全一致，剑指 Offer 目录下同样维护了多语言实现。

由此可见，n & (n - 1)这类「消位」技巧是贯穿位运算题目的一条主线，掌握原理后可迁移到判断 2 的幂、统计 1 的个数、检测进位等一大批问题上。

七、总结

「位 1 的个数」虽然是一道简单题，却浓缩了位运算的三重考察点：与运算取低位、逻辑右移的语义、以及n & (n - 1)消位技巧。通过仓库文档 + 三语言源码的对照阅读，读者既能从原理上理解两种算法的循环次数差异（O(log n) vs O(M)），也能从 Java 的>>>、C++ 的uint32_t等实现细节中体会到「无符号语义」在不同语言中的落地差异。建议读者在本地运行 C++ 驱动用例，或为 Python / Java 骨架补入11、128（二进制10000000，含 1 个 1）、4294967293（二进制全 1 前 32 位，含 32 个 1）等边界输入，用输出结果验证本文的复杂度结论。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book