` 两种位运算解法剖析)
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的个数。这个问题在工程与面试中之所以高频出现是因为它考察两个基础且重要的能力位运算基本功与、或|、异或^、取反~、左移、右移的语义与组合运用对「无符号数」语义的理解题目把输入视为无符号整数因此高位补位的行为必须明确逻辑右移 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即最低位」的性质可以设计如下循环初始化数量统计变量res 0循环逐位判断当n 0时跳出res n 1若n 1 1则统计数res加一n 1将二进制数字n无符号右移一位返回统计数量res。整个流程等价于每次只「看」最低位看完就右移丢弃直到n变为0。3.2 三种语言实现与无符号右移的差异仓库文档与源码中三语言实现思路完全一致但右移写法因语言特性而不同Pythonlc_191_number_of_1_bits_s1.pyclass Solution: def hammingWeight(self, n: int) - int: res 0 while n: res n 1 n 1 return resPython 的整数是任意精度、非负数按位存储对非负输入使用即等价于逻辑右移因此直接n 1即可无需区分算术右移与逻辑右移。Javalc_191_number_of_1_bits_s1.javapublic 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时终止。这正是本题最容易踩的坑也是源码选择的原因。Clc_191_number_of_1_bits_s1.cppclass 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.cppint 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 算法流程初始化数量统计变量res循环消去最右边的1当n 0时跳出res 1统计变量加1n n - 1消去数字n最右边的1返回统计数量res。每轮循环必然消去一个1因此总循环次数等于1的个数 M。4.3 三种语言实现Pythonlc_191_number_of_1_bits_s2.pyclass Solution: def hammingWeight(self, n: int) - int: res 0 while n: res 1 n n - 1 return resJavalc_191_number_of_1_bits_s2.javapublic class Solution { public int hammingWeight(int n) { int res 0; while (n ! 0) { res; n n - 1; } return res; } }Clc_191_number_of_1_bits_s2.cppclass 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很少如稀疏的掩码值时方法二优势显著即使最坏情况如0xFFFFFFFFM 32循环次数也恒定为 32与位长相当整体上方法二通常更优。五、两种方法对比小结维度方法一逐位判断方法二n (n - 1)核心思想每次取最低位右移丢弃每次消去最右边的1循环次数log₂n最高位 1 所在位数M二进制中 1 的个数时间复杂度O(log n)O(M)空间复杂度O(1)O(1)语言差异点Java 必须用C 依赖uint32_t三语言写法一致无右移方向顾虑典型适用通用、易理解、适合初学稀疏 1 场景更高效是面试推荐写法两种解法均已收录于 docs/191. 位1的个数.md 的「方法一逐位判断」与「方法二巧用n (n - 1)」两节仓库内代码目录lc_191_number_of_1_bitsJava、C与lc_191_number_of_1_bits_s1/s2.pyPython一一对应命名中的_s1/_s2即解法序号方便对照查阅。六、位运算专题在仓库中的延伸理解本题后可以沿着仓库的位运算专题继续深挖同类思想在多题中复用只出现一次的数字利用异或^的「自反性」在 O(n) 时间内找出唯一出现一次的数字对应源码 lc_136_single_number.py两整数之和在不使用加减法的约束下用「与运算 左移」求进位、用异或求无进位和递归迭代完成加法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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：位 1 的个数（191. Number of 1 Bits）——逐位判断与 `n (n - 1)` 两种位运算解法剖析
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的个数。这个问题在工程与面试中之所以高频出现是因为它考察两个基础且重要的能力位运算基本功与、或|、异或^、取反~、左移、右移的语义与组合运用对「无符号数」语义的理解题目把输入视为无符号整数因此高位补位的行为必须明确逻辑右移 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即最低位」的性质可以设计如下循环初始化数量统计变量res 0循环逐位判断当n 0时跳出res n 1若n 1 1则统计数res加一n 1将二进制数字n无符号右移一位返回统计数量res。整个流程等价于每次只「看」最低位看完就右移丢弃直到n变为0。3.2 三种语言实现与无符号右移的差异仓库文档与源码中三语言实现思路完全一致但右移写法因语言特性而不同Pythonlc_191_number_of_1_bits_s1.pyclass Solution: def hammingWeight(self, n: int) - int: res 0 while n: res n 1 n 1 return resPython 的整数是任意精度、非负数按位存储对非负输入使用即等价于逻辑右移因此直接n 1即可无需区分算术右移与逻辑右移。Javalc_191_number_of_1_bits_s1.javapublic 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时终止。这正是本题最容易踩的坑也是源码选择的原因。Clc_191_number_of_1_bits_s1.cppclass 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.cppint 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 算法流程初始化数量统计变量res循环消去最右边的1当n 0时跳出res 1统计变量加1n n - 1消去数字n最右边的1返回统计数量res。每轮循环必然消去一个1因此总循环次数等于1的个数 M。4.3 三种语言实现Pythonlc_191_number_of_1_bits_s2.pyclass Solution: def hammingWeight(self, n: int) - int: res 0 while n: res 1 n n - 1 return resJavalc_191_number_of_1_bits_s2.javapublic class Solution { public int hammingWeight(int n) { int res 0; while (n ! 0) { res; n n - 1; } return res; } }Clc_191_number_of_1_bits_s2.cppclass 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很少如稀疏的掩码值时方法二优势显著即使最坏情况如0xFFFFFFFFM 32循环次数也恒定为 32与位长相当整体上方法二通常更优。五、两种方法对比小结维度方法一逐位判断方法二n (n - 1)核心思想每次取最低位右移丢弃每次消去最右边的1循环次数log₂n最高位 1 所在位数M二进制中 1 的个数时间复杂度O(log n)O(M)空间复杂度O(1)O(1)语言差异点Java 必须用C 依赖uint32_t三语言写法一致无右移方向顾虑典型适用通用、易理解、适合初学稀疏 1 场景更高效是面试推荐写法两种解法均已收录于 docs/191. 位1的个数.md 的「方法一逐位判断」与「方法二巧用n (n - 1)」两节仓库内代码目录lc_191_number_of_1_bitsJava、C与lc_191_number_of_1_bits_s1/s2.pyPython一一对应命名中的_s1/_s2即解法序号方便对照查阅。六、位运算专题在仓库中的延伸理解本题后可以沿着仓库的位运算专题继续深挖同类思想在多题中复用只出现一次的数字利用异或^的「自反性」在 O(n) 时间内找出唯一出现一次的数字对应源码 lc_136_single_number.py两整数之和在不使用加减法的约束下用「与运算 左移」求进位、用异或求无进位和递归迭代完成加法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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考