191. 位1的个数（简单）

Blind 75 › 191. 位1的个数（简单）（第 1 章）

题目

给定一个正整数 n，把 n 写成二进制形式，求其中数字 1 的个数。这个个数也叫 汉明重量（Hamming Weight），或“设置位个数 / population count”。

注意本题只看二进制里出现了几个 1，不关心 1 出现在哪一位。

自造示例：

十进制 n	二进制	1 的个数
13	1101	3
64	1000000	1
255	11111111	8

约束：1 ≤ n ≤ 2³¹ − 1。也就是说输入一定为正，且最多不超过 31 个二进制位。

思路

一句话：不断擦掉 n 二进制里最右边的那个 1，擦一次计数一次，擦到 0 时计数就是答案。

最直白的做法是把 n 转成二进制字符串，再数有几个 '1'，例如 Python 的 bin(n).count("1")。它能过本题，但要额外生成字符串，而且没有用到本题真正想训练的“位操作直觉”。

更“位操作”一点的做法是逐位看最低位：

用 n & 1 取最低位是否等于 1。
用 n = n >> 1 丢掉最低位。

这样最多扫 32 位。它已经足够简单，但缺点是：中间的 0 也要白白走一遍。比如 1000000 只有一个 1，逐位法也要把这一串 0 全部右移完。

关键观察：对一个正数 n，n - 1 会把 最右边的 1 变成 0，并把它右边所有的 0 变成 1。

如 n = 1100，则 n - 1 = 1011。
此时 n & (n - 1) = 1100 & 1011 = 1000，恰好只把最右边的 1 擦掉了。

于是我们选定 Kernighan 算法：每执行一次 n = n & (n - 1)，就精确消去一个 1。有多少个 1，循环就执行多少次。

做法	要“看”多少个二进制位	额外空间
转字符串数字符	全部位，且生成字符串	O(位数)
逐位取最低位再右移	到最高位 1 为止，0 也走一遍	O(1)
擦最低位 1（本文）	只走 1 的个数次	O(1)

解法

先记住核心公式，再按步骤写：

把答案 count 初始化为 0。
当 n 不为 0 时，执行 n = n & (n - 1)，擦掉当前最低位的 1。
每擦掉一个 1，就令 count 加 1。
循环结束后返回 count。

以 n = 13（二进制 1101）为例：

轮次	本轮 n	n – 1	n & (n – 1)	count
初始	1101	—	—	0
1	1101	1100	1100	1
2	1100	1011	1000	2
3	1000	0111	0000	3

n 变为 0，正好循环 3 次，返回 3。

下图把上面 4 个步骤串成流程，并逐步演示：

191. 位1的个数（简单）解法步骤流程图 — 图① 解法步骤流程图（共 4 步）。

191. 位1的个数（简单）按步骤逐步执行的动画 — 动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →

class Solution {
public:
 int hammingWeight(uint32_t n) {
 int count = 0;
 while (n != 0) {
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。

一木科技

一木科技