LeetCode 191 位1的个数Hamming Weight四解法全解位掩码、移位与内置函数【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本篇基于仓库中 articles/number-of-one-bits.md 的完整解题框架系统讲解 LeetCode 191「位1的个数」Number of 1 Bits的四种经典解法逐位掩码Bit Mask、逐位右移Shift LSB、Brian Kernighan 最优算法n (n-1)以及各语言内置位计数函数。文章覆盖 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言的对照实现并给出时间与空间复杂度分析、常见陷阱有符号与无符号右移、除法和移位的差异同时结合仓库源码python/0191-number-of-1-bits.py、cpp/0191-number-of-1-bits.cpp、go/0191-number-of-1-bits.go、javascript/0191-number-of-1-bits.js印证各解法在真实代码库中的落地写法。读完后你将掌握位运算计数从朴素到最优的完整进阶路径并能直接迁移到布隆过滤器、校验和计算、图像二值化等真实场景。前置知识读懂二进制与位运算在动手解题前需要先掌握四个基础概念它们是本题所有解法的共同地基二进制数表示Binary Number Representation整数在内存中以比特bit序列存储每一位只能是0或1。例如11的 32 位二进制表示为0000 0000 0000 0000 0000 0000 0000 1011其中共有 3 个1。按位与运算符Bitwise ANDa b在两个操作数对应位都为1时才输出1因此n mask可以用来检测n中某一位是否被置位mask 该位为1其余位为0结果非零说明该位为1。位移动Bit Shifting左移x i把x的二进制位整体向左移动i位低位补0等价于乘以2^i右移x i整体向右移动i位等价于除以2^i对有符号负数注意算术移位填充1的问题见后文陷阱小节。移位既可以把单个1送到任意位置构造掩码也可以把目标位逐步送到最低位进行检测。关键位运算技巧n (n - 1)会清除n最右侧的那个1位。这一性质来自减法的借位机制n - 1会把最右侧的1变成0并把其右边所有0变成1再与n做按位与这些被翻转的位全部归零恰好只消掉最右侧的1。仓库中 hints/number-of-one-bits.md 的提示也印证了上述方向题目给出的是 32 位整数可以借助位运算符迭代每一位用(1 i)构造在第i位为1的掩码再通过按位与判断该位是否被置位。解法一Bit Mask逐位掩码检测思路Intuition题目要求统计整数n的二进制表示中1的个数这个值在计算机科学中被称为汉明重量Hamming Weight或人口计数population count。最直观的思路是逐位检查整数通常用 32 位表示因此安全地检查全部 32 个位位置即可。对每一个位置i用1 i构造一个只在第i位为1的掩码用mask n判断n的第i位是否被置位。算法步骤初始化计数器res 0。对位位置i从0到31循环构造掩码mask 1 i只有第i位为1。检测该位若(mask n) ! 0则res加一。32 个位置全部检查完毕后返回res。多语言实现class Solution: def hammingWeight(self, n: int) - int: res 0 for i in range(32): if (1 i) n: res 1 return respublic class Solution { public int hammingWeight(int n) { int res 0; for (int i 0; i 32; i) { if ((1 i n) ! 0) { res; } } return res; } }class Solution { public: int hammingWeight(uint32_t n) { int res 0; for (int i 0; i 32; i) { if ((1 i) n) { res; } } return res; } };class Solution { /** * param {number} n - a positive integer * return {number} */ hammingWeight(n) { let res 0; for (let i 0; i 32; i) { if ((1 i) n) { res; } } return res; } }public class Solution { public int HammingWeight(uint n) { int res 0; for (int i 0; i 32; i) { if ((1 i n) ! 0) { res; } } return res; } }func hammingWeight(n int) int { res : 0 for i : 0; i 32; i { if (1i)n ! 0 { res } } return res }class Solution { fun hammingWeight(n: Int): Int { var res 0 for (i in 0 until 32) { if ((1 shl i) and n ! 0) { res } } return res } }class Solution { func hammingWeight(_ n: Int) - Int { var res 0 for i in 0..32 { if (1 i) n ! 0 { res 1 } } return res } }impl Solution { pub fn hamming_weight(n: i32) - i32 { let mut res 0; for i in 0..32 { if (1 i) n ! 0 { res 1; } } res } }仓库中的 javascript/0191-number-of-1-bits.js 正是这一解法的工程化写法它用一个可变的mask变量从1开始每轮检测(n mask) ! 0后执行mask 1等价于依次使用1 0到1 31的全部掩码循环固定 32 次。复杂度分析时间复杂度$O(1)$固定循环 32 次与输入规模无关空间复杂度$O(1)$仅使用常量级计数器解法二Bit Mask II逐位右移 最低位检测思路Intuition第二种做法不再固定循环 32 次而是每次只看最低有效位LSB然后把数字右移一位让下一位进入最低位位置直到n变为0n 1判断当前最低位是否为1n 1把数字右移一位处理下一位。这样循环次数等于n的有效二进制位数不含高位多余的0通常远小于 32 次。算法步骤初始化计数器res 0。当n 0时循环若最低位为1n 1为真res加一执行n 1右移一位。n变为0时说明所有位已处理完毕。返回res。多语言实现class Solution: def hammingWeight(self, n: int) - int: res 0 while n: res 1 if n 1 else 0 n 1 return respublic class Solution { public int hammingWeight(int n) { int res 0; while (n ! 0) { res (n 1) 1 ? 1 : 0; n 1; } return res; } }class Solution { public: int hammingWeight(uint32_t n) { int res 0; while (n ! 0) { res (n 1) ? 1 : 0; n 1; } return res; } };class Solution { /** * param {number} n - a positive integer * return {number} */ hammingWeight(n) { let res 0; while (n ! 0) { res (n 1) 1 ? 1 : 0; n 1; } return res; } }public class Solution { public int HammingWeight(uint n) { int res 0; while (n ! 0) { res (n 1) 1 ? 1 : 0; n 1; } return res; } }func hammingWeight(n int) int { res : 0 for n ! 0 { if n1 ! 0 { res } n 1 } return res }class Solution { fun hammingWeight(n: Int): Int { var res 0 var num n while (num ! 0) { if ((num and 1) ! 0) { res } num num shr 1 } return res } }class Solution { func hammingWeight(_ n: Int) - Int { var n n var res 0 while n ! 0 { res (n 1) ! 0 ? 1 : 0 n 1 } return res } }impl Solution { pub fn hamming_weight(n: i32) - i32 { let mut n n; let mut res 0; while n ! 0 { res n 1; n 1; } res } }复杂度分析时间复杂度$O(1)$循环次数受限于 32 位整数最多 32 次空间复杂度$O(1)$解法三Bit MaskOptimal—— Brian Kernighan 算法思路Intuition前两种解法都需要检查那些值为0的位存在不必要的浪费。最优解法利用n (n - 1)的核心性质从n中减去1会把最右侧的1翻转成0并把其右侧所有位翻转成1再执行n (n - 1)这些被翻转的位全部归零等价于一步移除最右侧的一个1位。因此每次执行n n (n - 1)恰好消灭一个1位循环次数等于1的个数而不是固定 32 次或总位数——这就是它被称为最优解法的原因。以n 11二进制1011为例n (n-1)1011 1010 1010消掉一个1res 11010 1001 1000res 21000 0111 0000res 3n 0返回3。算法步骤初始化计数器res 0。当n不为0时循环执行n n (n - 1)移除最右侧的1位res加一。n变为0时所有1位均已移除。返回res。多语言实现class Solution: def hammingWeight(self, n: int) - int: res 0 while n: n n - 1 res 1 return respublic class Solution { public int hammingWeight(int n) { int res 0; while (n ! 0) { n n - 1; res; } return res; } }class Solution { public: int hammingWeight(uint32_t n) { int res 0; while (n) { n n - 1; res; } return res; } };class Solution { /** * param {number} n - a positive integer * return {number} */ hammingWeight(n) { let res 0; while (n ! 0) { n n - 1; res; } return res; } }public class Solution { public int HammingWeight(uint n) { int res 0; while (n ! 0) { n n (n - 1); res; } return res; } }func hammingWeight(n int) int { res : 0 for n ! 0 { n n - 1 res } return res }class Solution { fun hammingWeight(n: Int): Int { var res 0 var num n while (num ! 0) { num num and (num - 1) res } return res } }class Solution { func hammingWeight(_ n: Int) - Int { var n n var res 0 while n ! 0 { n (n - 1) res 1 } return res } }impl Solution { pub fn hamming_weight(n: i32) - i32 { let mut n n; let mut res 0; while n ! 0 { n n - 1; res 1; } res } }仓库源码印证这一解法正是仓库多种语言提交中采用的标准答案形态python/0191-number-of-1-bits.py 中while n: n n - 1; res 1的写法与本文完全一致go/0191-number-of-1-bits.go 采用for num 0 { num num - 1; res 1 }并在函数签名中使用uint32无符号类型规避右移符号位问题cpp/0191-number-of-1-bits.cpp 在同一文件中同时给出了逐位检测版和 Kernighan 版注释明确标注 use kernighans algorithm to only iterate num(set bits) times并特别指出本解法只迭代置位位数那么多次与本文的最优性分析互相印证。复杂度分析时间复杂度$O(1)$更精确地说是 $O(\text{set bits})$最坏 32 次空间复杂度$O(1)$解法四内置函数Built-In Function思路Intuition大多数编程语言都提供了二进制转换或统计置位数的内置工具例如bin(n)、Integer.bitCount、__builtin_popcount、countOneBits、nonzeroBitCount等。直接用这些 API 可以让代码简短、易读、不易出错尤其适合初学者理解题意后快速验证。需要注意的是本解法的定位是清晰与简洁优先而非追求底层微优化对绝大多数场景而言其底层实现与手写位运算同样高效。算法步骤用语言提供的内置二进制转换或位计数工具处理输入n。统计二进制表示中1的个数。返回统计结果。多语言实现class Solution: def hammingWeight(self, n: int) - int: return bin(n).count(1)public class Solution { public int hammingWeight(int n) { return Integer.bitCount(n); } }class Solution { public: int hammingWeight(uint32_t n) { return __builtin_popcount(n); } };class Solution { /** * param {number} n - a positive integer * return {number} */ hammingWeight(n) { return n.toString(2).split(0).join().length; } }public class Solution { public int HammingWeight(uint n) { return System.Numerics.BitOperations.PopCount(n); } }func hammingWeight(n int) int { return bits.OnesCount(uint(n)) }class Solution { fun hammingWeight(n: Int): Int { return n.countOneBits() } }class Solution { func hammingWeight(_ n: Int) - Int { return n.nonzeroBitCount } }impl Solution { pub fn hamming_weight(n: i32) - i32 { n.count_ones() as i32 } }各语言内置工具的对应关系速查语言内置 API说明Pythonbin(n).count(1)先转二进制字符串再统计1字符JavaInteger.bitCount(n)标准库位计数方法C__builtin_popcount(n)GCC/Clang 内建函数通常映射到 CPU 指令JavaScriptn.toString(2).split(0).join().length转二进制字符串后统计非零字符C#System.Numerics.BitOperations.PopCount(n).NET 硬件加速位计数Gobits.OnesCount(uint(n))math/bits包注意需要显式转换为uintKotlinn.countOneBits()Kotlin 标准库扩展Swiftn.nonzeroBitCountSwift 标准库属性Rustn.count_ones()Rust 标准库方法复杂度分析时间复杂度$O(1)$内置实现通常映射到硬件指令或常数次运算空间复杂度$O(1)$注意 JavaScript 与 Python 的字符串转换路径会临时产生 $O(32)$ 的字符串空间常见陷阱Common Pitfalls陷阱一有符号与无符号整数的处理在某些语言中对有符号负数执行右移时采用的是算术右移高位补1而不是0。这会导致while (n ! 0)中的n永远无法变为0从而陷入死循环。规避方法有三种使用无符号类型如 C/Go 中的uint32_t/uint32仓库的 cpp/0191-number-of-1-bits.cpp 与 go/0191-number-of-1-bits.go 都采用了这一做法使用逻辑右移运算符如 Java 的无符号右移高位补0代替使用固定 32 次的循环解法一或n (n - 1)解法三这两种做法不依赖右移对符号位的处理。陷阱二用除法代替位右移n / 2与n 1对正整数的结果相同但两者有本质区别对负数的行为不同是向下取整向负无穷而部分语言的整数除法是向零取整结果不一致性能不同位右移是单条 CPU 指令除法通常更慢。因此本题应坚持使用位运算既保证行为一致也符合题目考察位操作的意图。四种解法对比与实战选择解法核心操作循环次数特点解法一逐位掩码(1 i) n固定 32 次最直观与符号无关适合教学与入门解法二右移 LSB(n 1)n 1有效位数次最多 32代码简洁需注意负数右移陷阱解法三Kernighann (n - 1)置位个数次最快平均而言面试首选解法四内置函数语言内置 API常数最短最不易错适合快速实现实战建议面试中优先给出解法一建立直觉再演进到解法三展示对位运算性质的深入理解工程代码中可直接使用解法四的内置 APIGo 的bits.OnesCount、Java 的Integer.bitCount等底层往往已有硬件指令加速。n (n - 1)这一技巧除了本题之外还广泛用于判断2的幂n (n - 1) 0、枚举子集、位图遍历等经典位运算场景值得单独记牢。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考