LeetCode-Book 题解精读：LCR 133「位 1 的个数」两种位运算方案逐行拆解

LeetCode-Book 题解精读：LCR 133「位 1 的个数」两种位运算方案逐行拆解

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

本篇以仓库 leetbook_ioa/docs/LCR 133. 位 1 的个数.md 为骨架，结合仓库中《Krahets 笔面试精选 88 题》与《剑指 Offer》两套题解的 Python / Java / C++ 源码，深入讲解统计二进制数中 1 的个数的两种经典位运算方案。读完本文，你将掌握「逐位判断」与「n & (n - 1)」两条完整解题链路，理解无符号右移在各语言中的差异，并能直接复用仓库源码完成验证。

题目背景：同一道题在三个系列中的位置

本仓库围绕同一道经典位运算题给出了多套对应题解：

• 《图解算法数据结构》（leetbook_ioa）：题号为 LCR 133. 位 1 的个数，即本题的主体文档；
• 《剑指 Offer》：对应 剑指 Offer 15. 二进制中 1 的个数；
• 《Krahets 笔面试精选 88 题》：对应 191. 位 1 的个数。

三处题目本质相同：给定一个无符号整数，返回其二进制表示中数字位数为 1 的个数（即汉明重量，Hamming Weight）。LeetCode 191、剑指 Offer 15、LCR 133 均要求同一实现hammingWeight(n)。

前置知识：读懂两种解法所需的位运算基础

原文档的两种解法只依赖两个基本位运算：

1. 与运算&

按位与，仅当两个对应位都为 1 时结果位为 1。因此：

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

这正是方法一能够逐位判定的依据。

2. 右移运算>>与无符号右移>>>

右移把二进制位整体向低位移动，高位补位规则因语言而异：

• C++ / Python：对无符号整数（uint32_t）右移时高位补 0，天然符合"把数字看作无符号数"的要求；
• Java：int n是有符号数，算术右移>>会按符号位补 1，必须改用逻辑右移>>>（无符号右移，高位一律补 0），否则负数会陷入无限循环。

原文档特别强调"本题要求把数字 n 看作无符号数"，这一点直接决定了 Java 实现必须使用>>>，也是新手最容易踩的坑。

方法一：逐位判断（与运算 + 无符号右移）

算法流程

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

整个过程相当于从最低位向最高位逐位扫描，遇到 1 就计数，直到n变为 0。原文档中配有逐位演算示意图，直观展示了n = 11（二进制1011）从右往左依次判定1, 1, 0, 1的过程。

三种语言实现（仓库源码级对照）

# leetbook_ioa / selected_coding_interview / sword_for_offer 三处 Python 解法一致 class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n: res += n & 1 n >>= 1 return res

// Java 必须使用无符号右移 >>>，否则负数无法终止循环 public class Solution { public int hammingWeight(int n) { int res = 0; while (n != 0) { res += n & 1; n >>>= 1; } return res; } }

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

以上代码可在仓库以下路径找到对应可运行版本：

• Python：lc_191_number_of_1_bits_s1.py、sfo_15_number_of_1_bits_s1.py
• Java：lc_191_number_of_1_bits_s1.java
• C++：lc_191_number_of_1_bits_s1.cpp

其中 C++ 版本自带了完整驱动测试，使用uint32_t n = 0b00000000000000000000000000001011;（十进制 11，含 3 个 1）作为测试用例并直接打印结果，可直接编译运行验证。

复杂度分析

• 时间复杂度 O(log₂n)：循环内部仅有移位、与、加等基本运算，单次开销 O(1)；逐位判断需要循环 log₂n 次，其中 log₂n 表示数字 n 最高位 1 所在位数（例如 log₂4 = 2，log₂16 = 4）；
• 空间复杂度 O(1)：仅使用常数大小的变量res。

方法二：巧用 n & (n - 1)（每轮消去最右的 1）

两个关键结论的推导

• (n - 1)的作用：二进制数字n最右边的1变成0，这个1右边的所有0都变成1；
• n & (n - 1)的作用：二进制数字n最右边的1变成0，其余位保持不变。

原文档用图示展示了这一性质：例如n = 0b101100，n - 1 = 0b101011，两者相与得到0b101000，最右边的 1 被精准消去。由于每次运算恰好消去一个 1，循环次数等于 1 的个数，天然与输入规模解耦。

算法流程

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

三种语言实现

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

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

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

仓库对应实现：

• Python：lc_191_number_of_1_bits_s2.py、sfo_15_number_of_1_bits_s2.py
• Java：lc_191_number_of_1_bits_s2.java
• C++：lc_191_number_of_1_bits_s2.cpp

C++ 版同样内置n = 0b...00001011测试用例；剑指 Offer 的 Python 版则直接以n = 11驱动并print(res)输出 3，sfo_15_number_of_1_bits_s2.py 可以直接运行复现。

复杂度分析

• 时间复杂度 O(M)：n & (n - 1)仅含减法和与运算，单次开销 O(1)；设 M 为二进制数字 n 中 1 的个数，每轮消去一个 1，共循环 M 次，整体 O(M)；
• 空间复杂度 O(1)：仅使用常数大小的变量res。

两种方法对比与选型建议

两种方案的空间复杂度均为 O(1)。方法一胜在直观、易于推导，且天然适合需要同时"取出每一位"的场景；方法二n & (n - 1)是位运算中极具代表性的技巧，不仅用于本题，还常见于判断一个数是否为 2 的整数次幂、计算最低位 1 的位置等进阶题目，值得单独记忆。

仓库实证：三套题解互相印证

从仓库结构可以确认，这道题在三个系列中被完整收录，且解法一一对应：

• 《图解算法数据结构》LCR 133. 位 1 的个数.md 与《笔面试精选 88 题》191. 位1的个数.md 的正文完全一致，均给出两种方法；
• 《剑指 Offer》目录下另有 剑指 Offer 15. 二进制中 1 的个数.md 及其 Python / Java / C++ 源码；
• 仓库中 Python 文件统一通过from include import *引入工具模块（见 include 目录），保持 Solution 代码与测试驱动分离的工程化组织方式。

这意味着你可以把本文所述任一方法放到三个系列的任意一处，得到完全一致的解题逻辑与复杂度结论——同一算法思想在不同题单中的一致性，本身就是复习时很好的交叉验证手段。

动手验证建议

1. 直接运行剑指 Offer 的 Python 版：python sfo_15_number_of_1_bits_s1.py，输入n = 11（二进制1011）应输出 3；
2. 修改n为0（应输出 0）、2^31（应输出 1）等边界值，对比两种方法结果一致；
3. 编译运行 C++ 版验证驱动代码，观察0b00000000000000000000000000001011的计数结果。

通过亲手运行仓库源码，你能更直观地体会到：方法一的循环次数取决于数值大小，方法二的循环次数取决于 1 的密度——这正是位运算题目"复杂度由二进制形态决定"的典型体现。

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