LeetCode 题解工作台
位1的个数
给定一个正整数 n ，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为 汉明重量 ）。 示例 1： 输入： n = 11 输出： 3 解释： 输入的二进制串 1011 中，共有 3 个设置位。 示例 2： 输入： n = 128 输出： 1 解释： 输入的二进…
2
题型
9
代码语言
3
相关题
当前训练重点
简单 · divide·conquer·结合·位运算·操作
答案摘要
利用 `n & (n - 1)` 消除 `n` 中最后一位 1 这一特点，优化过程： HAMMING-WEIGHT(n)
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 divide·conquer·结合·位运算·操作 题型思路
题目描述
给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。
示例 2：
输入：n = 128 输出：1 解释：输入的二进制串 10000000 中，共有 1 个设置位。
示例 3：
输入：n = 2147483645 输出：30 解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。
提示：
1 <= n <= 231 - 1
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？
解题思路
方法一：位运算
利用 n & (n - 1) 消除 n 中最后一位 1 这一特点，优化过程：
HAMMING-WEIGHT(n)
r = 0
while n != 0
n &= n - 1
r += 1
r
以 5 为例，演示推演过程：
[0, 1, 0, 1] // 5
[0, 1, 0, 0] // 5 - 1 = 4
[0, 1, 0, 0] // 5 & 4 = 4
[0, 1, 0, 0] // 4
[0, 0, 1, 1] // 4 - 1 = 3
[0, 0, 0, 0] // 4 & 3 = 0
class Solution:
def hammingWeight(self, n: int) -> int:
ans = 0
while n:
n &= n - 1
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The interviewer wants bit-level reasoning, not string conversion or decimal digit counting.
- question_mark
A follow-up about optimization usually points toward n &= n - 1 instead of checking every position.
- question_mark
If divide and conquer appears in the topic list, explain how each bit-clearing step shrinks the remaining subproblem.
常见陷阱
外企场景- error
Counting decimal 1s in the number instead of set bits in the binary representation.
- error
Using string conversion first, which hides the bit manipulation pattern this problem is testing.
- error
Forgetting that n &= n - 1 removes exactly one set bit, not one arbitrary bit.
进阶变体
外企场景- arrow_right_alt
Return whether the number has exactly one set bit, which turns the problem into a power-of-two style check.
- arrow_right_alt
Count set bits for every number from 0 to n, which leads to a dynamic programming bit-count array.
- arrow_right_alt
Handle negative values in a fixed-width language, where unsigned interpretation matters for bit operations.