企业官网建设流程全解析

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 AND，&）：a & 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. 用1 << i构造一个只在第i位为1的掩码；
2. 用mask & n判断n的第i位是否被置位。

算法步骤

1. 初始化计数器res = 0。
2. 对位位置i从0到31循环：
3. 构造掩码mask = 1 << i（只有第i位为1）。
4. 检测该位：若(mask & n) != 0，则res加一。
5. 32 个位置全部检查完毕后，返回res。

多语言实现

class Solution: def hammingWeight(self, n: int) -> int: res = 0 for i in range(32): if (1 << i) & n: res += 1 return res

public 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 (1<<i)&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变为0：

• n & 1判断当前最低位是否为1；
• n >>= 1把数字右移一位，处理下一位。

这样循环次数等于n的有效二进制位数（不含高位多余的0），通常远小于 32 次。

算法步骤

1. 初始化计数器res = 0。
2. 当n > 0时循环：
   • 若最低位为1（n & 1为真），res加一；
   • 执行n >>= 1右移一位。
3. n变为0时说明所有位已处理完毕。
4. 返回res。

多语言实现

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

public 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 n&1 != 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 Mask（Optimal）—— 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）为例：

1. n & (n-1)：1011 & 1010 = 1010，消掉一个1，res = 1；
2. 1010 & 1001 = 1000，res = 2；
3. 1000 & 0111 = 0000，res = 3；
4. n = 0，返回3。

算法步骤

1. 初始化计数器res = 0。
2. 当n不为0时循环：
   • 执行n = n & (n - 1)移除最右侧的1位；
   • res加一。
3. n变为0时所有1位均已移除。
4. 返回res。

多语言实现

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

public 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 kernighan's 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 可以让代码简短、易读、不易出错，尤其适合初学者理解题意后快速验证。

需要注意的是，本解法的定位是清晰与简洁优先，而非追求底层微优化；对绝大多数场景而言其底层实现与手写位运算同样高效。

算法步骤

1. 用语言提供的内置二进制转换或位计数工具处理输入n。
2. 统计二进制表示中1的个数。
3. 返回统计结果。

多语言实现

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 } }

各语言内置工具的对应关系速查：

复杂度分析

• 时间复杂度：$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 指令，除法通常更慢。

因此本题应坚持使用位运算，既保证行为一致，也符合题目考察位操作的意图。

四种解法对比与实战选择

实战建议：面试中优先给出解法一建立直觉，再演进到解法三展示对位运算性质的深入理解；工程代码中可直接使用解法四的内置 API（Go 的bits.OnesCount、Java 的Integer.bitCount等底层往往已有硬件指令加速）。n & (n - 1)这一技巧除了本题之外，还广泛用于判断2的幂（n & (n - 1) == 0）、枚举子集、位图遍历等经典位运算场景，值得单独记牢。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode