` 位运算统计二进制中 1 的个数（汉明重量）)
LeetCode 191 Number of 1 Bits 题解用n (n - 1)位运算统计二进制中 1 的个数汉明重量【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇文章基于开源仓库 leetcode 中的 191.number-of-1-bits.en.md 展开。题目要求统计一个无符号整数的二进制表达式中1的个数也就是经典的**汉明重量Hamming Weight**问题。读完本文你将掌握n (n - 1)这一消除最低位1的核心位运算技巧、多语言实现JS / C / Python / Java、复杂度分析方法以及基于掩码分治的 O(1) 常数时间扩展解法并能在实际面试与工程场景中举一反三。题目描述编写一个函数输入是一个无符号整数返回其二进制表达式中数字位数为1的个数也被称为汉明重量。示例 1输入00000000000000000000000000001011 输出3 解释输入的二进制串 00000000000000000000000000001011 中共有三位为 1。示例 2输入00000000000000000000000010000000 输出1 解释输入的二进制串 00000000000000000000000010000000 中共有一位为 1。示例 3输入11111111111111111111111111111101 输出31 解释输入的二进制串 11111111111111111111111111111101 中共有 31 位为 1。提示请注意在某些语言如 Java中没有无符号整数类型。在这种情况下输入和输出都将被指定为有符号整数类型并且不应影响实现因为无论整数是有符号的还是无符号的其内部的二进制表示形式都是相同的。在 Java 中编译器使用二进制补码记法来表示有符号整数因此在示例 3 中输入实际表示的是有符号整数-3。进阶如果这个函数会被多次调用你将如何优化算法前置知识本题目属于典型的位运算Bit Operation问题。仓库在 thinkings/bit.md 中系统整理了位运算套路并以 136、137、260、645 等题目为例讲解了异或的性质与用法异或运算a ^ b按位计算相同为 0、不同为 1任何数与自身异或为0任何数与0异或为自身异或满足交换律a ^ b ^ c a ^ c ^ b。在阅读本篇文章之前建议先熟悉二进制的位与、位或|、左移、右移等基础位运算这对理解后面消除1的原理与分治掩码扩展会很有帮助。该题在 collections/easy.en.md 中被收录为简单题可见其解法思路直观、代码量小但背后的位运算原理却非常值得深挖。核心思路n (n - 1)消除最低位的 1这个题目的大意是给定一个无符号整数返回其用二进制表示时1的个数。最朴素的想法是逐位检查例如 Java 解法中常见的n (1 i)循环 32 次但这里有一个经典的 trick可以非常优雅地求解——n (n - 1)可以消除n最低位最右边的那一个1。为什么能消除最后一个1原理其实比较简单当n的二进制末位为1即n为奇数时n - 1只是把末位的1变成0其余位不变两者相与后末位归零其余位保持原样等价于把最低位的1清零当n的二进制末位为0即n为偶数时n - 1需要向低位连续借位其效果是从最低位开始直到遇到第一个1为止低位连续的0全部变为1而那个1变为0。此时n (n - 1)恰好把从低到高第一个1及其更低位的所有位全部清零。例如n 12二进制为1100则n - 1 11二进制为1011两者相与得到1000即8。可以看到1100中最低位的那个1从右往左第三位被消除同时更低位也全部归零。基于这一原理我们可以不断执行n n (n - 1)直到n 0说明已经没有一个1了。此时我们消除了多少个1就说明n原本有多少个1——每次迭代消除恰好一个1因此循环次数就等于答案本身。关键点解析n (n - 1)消除最低位 1 的原理这是整个题目的灵魂利用它可以直接把循环次数从32 次降为二进制中 1 的个数次显著简化操作位运算思维遇到数字统计、二进制相关问题优先考虑位运算方案往往能获得比字符串转换或逐位移位更简洁的实现。代码实现原文档在 191.number-of-1-bits.en.md 中给出了 JS、C、Python 三种语言的实现仓库中文版 191.number-of-1-bits.md 还补充了 Java 逐位检查版本这里一并收录。JavaScript/* * lc appleetcode id191 langjavascript * */ /** * param {number} n - a positive integer * return {number} */ var hammingWeight function (n) { let count 0; while (n ! 0) { n n (n - 1); count; } return count; };Cclass Solution { public: int hammingWeight(uint32_t v) { auto count 0; while (v ! 0) { v (v - 1); count; } return count; } };注意 C 版本将参数类型声明为uint32_t直接利用无符号整型的语义无需关心符号位的干扰。Pythonclass Solution(object): def hammingWeight(self, n): :type n: int :rtype: int count 0 while n: n n - 1 count 1 return countPython 中while n在n为0时自动结束循环代码非常简洁。Java逐位检查public class Solution { public int hammingWeight(int n) { int count 0; for (int i 0; i 32; i) { if ((n (1 i)) ! 0) { count; } } return count; } }Java 版本使用n (1 i)依次检查 32 个二进制位体现了逐位统计的基础思路其循环次数固定为 32 次。复杂度分析时间复杂度原文档标注为 $O(logN)$。更准确地说基于n (n - 1)的解法循环次数等于二进制中1的个数记为 $k$最坏情况下如n 0xFFFFFFFF$k 32$在 32 位整数的前提下也可以理解为常数时间内可完成$O(1)$。相比固定循环 32 次的逐位检查法当输入中1较少时效率明显更高。空间复杂度原文档标注为 $O(N)$。从上述所有实现看循环内仅使用一个计数变量未申请任何与输入规模相关的额外存储实际空间复杂度应为 $O(1)$原文档的 $O(N)$ 应视为笔误。扩展利用掩码分治的常数时间解法除了迭代消除1还可以使用位操作分治也称 SWARSIMD Within A Register在常数时间内完成统计这也是进阶多次调用时如何优化的一种重要思路。原文档以 8 位的整数21二进制00010101为例演示了这种分治统计过程。其核心思想是先统计相邻 1 位中的1的个数结果用 2 位二进制表示再统计相邻 2 位中的1的个数结果用 4 位二进制表示以此类推每轮将相邻块合并最终得到整个 32 位整数中1的总数。每一轮只需要常数次位与、移位和加法因此整体是 $O(1)$ 时间且不依赖输入中1的个数非常适合被高频反复调用。C 代码如下来自 191.number-of-1-bits.en.mdconst uint32_t ODD_BIT_MASK 0xAAAAAAAA; const uint32_t EVEN_BIT_MASK 0x55555555; const uint32_t ODD_2BIT_MASK 0xCCCCCCCC; const uint32_t EVEN_2BIT_MASK 0x33333333; const uint32_t ODD_4BIT_MASK 0xF0F0F0F0; const uint32_t EVEN_4BIT_MASK 0x0F0F0F0F; const uint32_t ODD_8BIT_MASK 0xFF00FF00; const uint32_t EVEN_8BIT_MASK 0x00FF00FF; const uint32_t ODD_16BIT_MASK 0xFFFF0000; const uint32_t EVEN_16BIT_MASK 0x0000FFFF; class Solution { public: int hammingWeight(uint32_t v) { v (v EVEN_BIT_MASK) ((v ODD_BIT_MASK) 1); v (v EVEN_2BIT_MASK) ((v ODD_2BIT_MASK) 2); v (v EVEN_4BIT_MASK) ((v ODD_4BIT_MASK) 4); v (v EVEN_8BIT_MASK) ((v ODD_8BIT_MASK) 8); return (v EVEN_16BIT_MASK) ((v ODD_16BIT_MASK) 16); } };各掩码的作用0x555555550101...保留偶数位从 0 开始计用于统计相邻 1 位的和0xAAAAAAAA1010...保留奇数位配合右移 1 位后与偶数位相加得到每 2 位内的1个数0x33333333、0xCCCCCCCC、0x0F0F0F0F、0xF0F0F0F0等依次将统计粒度从 2 位扩展到 4 位、8 位、16 位直到合并出完整的 32 位结果。进阶问题的进一步思考题目结尾提出如果多次调用这个函数你将如何优化算法针对这一进阶场景除了上述分治SWAR常数时间方案外还可以考虑查表法将 8 位或 16 位整数的汉明重量预先存入查找表统计 32 位整数时拆成 4 个或 2 个字节查表求和。预计算一次、查询无数次适合海量重复调用的场景分治SWAR如上文 C 实现每轮并行统计相邻块内的1固定迭代次数无循环、无查表指令级开销极低。从仓库源码结构看本题位于 collections/easy.en.md 的简单题列表且 SUMMARY.md 将其收录在位运算专题之下与 190.reverse-bits.md颠倒二进制位、201数字范围按位与、898子数组按位或等题目共同构成位运算练习主线。建议在掌握本题的n (n - 1)技巧后继续练习 190.reverse-bits.md该题同样运用了位运算的掩码分治扩展相邻 1 位交换、2 位交换、4 位交换……直至 16 位交换两题互为镜像、相互印证可以一举吃透位运算的常见套路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 191 Number of 1 Bits 题解：用 `n (n - 1)` 位运算统计二进制中 1 的个数（汉明重量）
LeetCode 191 Number of 1 Bits 题解用n (n - 1)位运算统计二进制中 1 的个数汉明重量【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇文章基于开源仓库 leetcode 中的 191.number-of-1-bits.en.md 展开。题目要求统计一个无符号整数的二进制表达式中1的个数也就是经典的**汉明重量Hamming Weight**问题。读完本文你将掌握n (n - 1)这一消除最低位1的核心位运算技巧、多语言实现JS / C / Python / Java、复杂度分析方法以及基于掩码分治的 O(1) 常数时间扩展解法并能在实际面试与工程场景中举一反三。题目描述编写一个函数输入是一个无符号整数返回其二进制表达式中数字位数为1的个数也被称为汉明重量。示例 1输入00000000000000000000000000001011 输出3 解释输入的二进制串 00000000000000000000000000001011 中共有三位为 1。示例 2输入00000000000000000000000010000000 输出1 解释输入的二进制串 00000000000000000000000010000000 中共有一位为 1。示例 3输入11111111111111111111111111111101 输出31 解释输入的二进制串 11111111111111111111111111111101 中共有 31 位为 1。提示请注意在某些语言如 Java中没有无符号整数类型。在这种情况下输入和输出都将被指定为有符号整数类型并且不应影响实现因为无论整数是有符号的还是无符号的其内部的二进制表示形式都是相同的。在 Java 中编译器使用二进制补码记法来表示有符号整数因此在示例 3 中输入实际表示的是有符号整数-3。进阶如果这个函数会被多次调用你将如何优化算法前置知识本题目属于典型的位运算Bit Operation问题。仓库在 thinkings/bit.md 中系统整理了位运算套路并以 136、137、260、645 等题目为例讲解了异或的性质与用法异或运算a ^ b按位计算相同为 0、不同为 1任何数与自身异或为0任何数与0异或为自身异或满足交换律a ^ b ^ c a ^ c ^ b。在阅读本篇文章之前建议先熟悉二进制的位与、位或|、左移、右移等基础位运算这对理解后面消除1的原理与分治掩码扩展会很有帮助。该题在 collections/easy.en.md 中被收录为简单题可见其解法思路直观、代码量小但背后的位运算原理却非常值得深挖。核心思路n (n - 1)消除最低位的 1这个题目的大意是给定一个无符号整数返回其用二进制表示时1的个数。最朴素的想法是逐位检查例如 Java 解法中常见的n (1 i)循环 32 次但这里有一个经典的 trick可以非常优雅地求解——n (n - 1)可以消除n最低位最右边的那一个1。为什么能消除最后一个1原理其实比较简单当n的二进制末位为1即n为奇数时n - 1只是把末位的1变成0其余位不变两者相与后末位归零其余位保持原样等价于把最低位的1清零当n的二进制末位为0即n为偶数时n - 1需要向低位连续借位其效果是从最低位开始直到遇到第一个1为止低位连续的0全部变为1而那个1变为0。此时n (n - 1)恰好把从低到高第一个1及其更低位的所有位全部清零。例如n 12二进制为1100则n - 1 11二进制为1011两者相与得到1000即8。可以看到1100中最低位的那个1从右往左第三位被消除同时更低位也全部归零。基于这一原理我们可以不断执行n n (n - 1)直到n 0说明已经没有一个1了。此时我们消除了多少个1就说明n原本有多少个1——每次迭代消除恰好一个1因此循环次数就等于答案本身。关键点解析n (n - 1)消除最低位 1 的原理这是整个题目的灵魂利用它可以直接把循环次数从32 次降为二进制中 1 的个数次显著简化操作位运算思维遇到数字统计、二进制相关问题优先考虑位运算方案往往能获得比字符串转换或逐位移位更简洁的实现。代码实现原文档在 191.number-of-1-bits.en.md 中给出了 JS、C、Python 三种语言的实现仓库中文版 191.number-of-1-bits.md 还补充了 Java 逐位检查版本这里一并收录。JavaScript/* * lc appleetcode id191 langjavascript * */ /** * param {number} n - a positive integer * return {number} */ var hammingWeight function (n) { let count 0; while (n ! 0) { n n (n - 1); count; } return count; };Cclass Solution { public: int hammingWeight(uint32_t v) { auto count 0; while (v ! 0) { v (v - 1); count; } return count; } };注意 C 版本将参数类型声明为uint32_t直接利用无符号整型的语义无需关心符号位的干扰。Pythonclass Solution(object): def hammingWeight(self, n): :type n: int :rtype: int count 0 while n: n n - 1 count 1 return countPython 中while n在n为0时自动结束循环代码非常简洁。Java逐位检查public class Solution { public int hammingWeight(int n) { int count 0; for (int i 0; i 32; i) { if ((n (1 i)) ! 0) { count; } } return count; } }Java 版本使用n (1 i)依次检查 32 个二进制位体现了逐位统计的基础思路其循环次数固定为 32 次。复杂度分析时间复杂度原文档标注为 $O(logN)$。更准确地说基于n (n - 1)的解法循环次数等于二进制中1的个数记为 $k$最坏情况下如n 0xFFFFFFFF$k 32$在 32 位整数的前提下也可以理解为常数时间内可完成$O(1)$。相比固定循环 32 次的逐位检查法当输入中1较少时效率明显更高。空间复杂度原文档标注为 $O(N)$。从上述所有实现看循环内仅使用一个计数变量未申请任何与输入规模相关的额外存储实际空间复杂度应为 $O(1)$原文档的 $O(N)$ 应视为笔误。扩展利用掩码分治的常数时间解法除了迭代消除1还可以使用位操作分治也称 SWARSIMD Within A Register在常数时间内完成统计这也是进阶多次调用时如何优化的一种重要思路。原文档以 8 位的整数21二进制00010101为例演示了这种分治统计过程。其核心思想是先统计相邻 1 位中的1的个数结果用 2 位二进制表示再统计相邻 2 位中的1的个数结果用 4 位二进制表示以此类推每轮将相邻块合并最终得到整个 32 位整数中1的总数。每一轮只需要常数次位与、移位和加法因此整体是 $O(1)$ 时间且不依赖输入中1的个数非常适合被高频反复调用。C 代码如下来自 191.number-of-1-bits.en.mdconst uint32_t ODD_BIT_MASK 0xAAAAAAAA; const uint32_t EVEN_BIT_MASK 0x55555555; const uint32_t ODD_2BIT_MASK 0xCCCCCCCC; const uint32_t EVEN_2BIT_MASK 0x33333333; const uint32_t ODD_4BIT_MASK 0xF0F0F0F0; const uint32_t EVEN_4BIT_MASK 0x0F0F0F0F; const uint32_t ODD_8BIT_MASK 0xFF00FF00; const uint32_t EVEN_8BIT_MASK 0x00FF00FF; const uint32_t ODD_16BIT_MASK 0xFFFF0000; const uint32_t EVEN_16BIT_MASK 0x0000FFFF; class Solution { public: int hammingWeight(uint32_t v) { v (v EVEN_BIT_MASK) ((v ODD_BIT_MASK) 1); v (v EVEN_2BIT_MASK) ((v ODD_2BIT_MASK) 2); v (v EVEN_4BIT_MASK) ((v ODD_4BIT_MASK) 4); v (v EVEN_8BIT_MASK) ((v ODD_8BIT_MASK) 8); return (v EVEN_16BIT_MASK) ((v ODD_16BIT_MASK) 16); } };各掩码的作用0x555555550101...保留偶数位从 0 开始计用于统计相邻 1 位的和0xAAAAAAAA1010...保留奇数位配合右移 1 位后与偶数位相加得到每 2 位内的1个数0x33333333、0xCCCCCCCC、0x0F0F0F0F、0xF0F0F0F0等依次将统计粒度从 2 位扩展到 4 位、8 位、16 位直到合并出完整的 32 位结果。进阶问题的进一步思考题目结尾提出如果多次调用这个函数你将如何优化算法针对这一进阶场景除了上述分治SWAR常数时间方案外还可以考虑查表法将 8 位或 16 位整数的汉明重量预先存入查找表统计 32 位整数时拆成 4 个或 2 个字节查表求和。预计算一次、查询无数次适合海量重复调用的场景分治SWAR如上文 C 实现每轮并行统计相邻块内的1固定迭代次数无循环、无查表指令级开销极低。从仓库源码结构看本题位于 collections/easy.en.md 的简单题列表且 SUMMARY.md 将其收录在位运算专题之下与 190.reverse-bits.md颠倒二进制位、201数字范围按位与、898子数组按位或等题目共同构成位运算练习主线。建议在掌握本题的n (n - 1)技巧后继续练习 190.reverse-bits.md该题同样运用了位运算的掩码分治扩展相邻 1 位交换、2 位交换、4 位交换……直至 16 位交换两题互为镜像、相互印证可以一举吃透位运算的常见套路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考