0Pricing
Competitive Programming Academy · 课时

统计位数与最低位的置位

使用 popcount 与 n & -n 技巧

统计位数与最低位的置位 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

统计 1 的个数

许多问题会询问一个数字中设置了多少位，这称为它的置位计数。它常用于子集大小、奇偶性检查和计分。🔢

Python 内置的计数方法

统计置位位最快的方法是整数方法 bit_count()。无需循环，也不麻烦，直接得到 1 的个数。

print((13).bit_count())  # 0b1101 has 3 ones

使用 bin 和 count 计数

如果您忘记了 bit_count，可以先将数字转换为二进制文本，再统计其中的 1。虽然速度较慢，但清晰易懂，也容易记住。

print(bin(13).count('1'))  # 3

最低置位位

最低置位位就是一个数字中最右侧的 1。将它单独取出，是之后处理树状数组和子集技巧的关键操作。

使用 n 和 -n 将其单独取出

著名技巧 n & -n 只保留最低置位位。补码中的负数让这个技巧能够奇妙地奏效。

n = 12  # 0b1100
print(n & -n)  # 4 = 0b100

为什么 n 和 -n 有效

取相反数会翻转所有位并加 1，因此最低的 1 以下的所有位都会发生反转。进行 AND 运算后，只剩下那个位。

去掉最低置位位

减去 1 时会借位穿过末尾的 0，因此 n & (n - 1) 会擦除最低置位位。重复执行即可逐个去掉所有的 1。

n = 12  # 0b1100
print(n & (n - 1))  # 8 = 0b1000

Brian Kernighan 计数法

当数字非零时循环，每次清除最低位。循环每个置位位执行一次，因此对于置位位稀疏的置位计数来说速度很快。

c = 0
while n:
    n &= n - 1
    c += 1

检查是否为 2 的幂

正的 2 的幂恰好只有一个置位位，因此 n & (n - 1) 等于 0。一次 AND 运算就能立即判断。

def is_pow2(n):
    return n > 0 and (n & (n - 1)) == 0

根据位计数判断奇偶性

一个数字的奇偶性就是其置位计数对 2 取模的结果。一步操作即可判断其中 1 的个数是奇数还是偶数。

parity = (13).bit_count() & 1  # 1

选择最快的工具

追求原始速度时使用 bit_count；要遍历置位位时使用 n & (n - 1) 循环。选择合适的工具，可以轻松应对严格的时间限制。⚡

快速检查

测试取出最低置位位的技巧。

回顾：统计位

您可以使用 bit_count 统计 1 的个数，使用 n & -n 取出最低位，并使用 n & (n - 1) 将其去掉。这些都是功能强大的一行写法。🎉

常见问题解答

「统计位数与最低位的置位」课时是免费的吗？

是的 — 「统计位数与最低位的置位」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「统计位数与最低位的置位」这节课中我会学到什么？

使用 popcount 与 n & -n 技巧 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

「统计位数与最低位的置位」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. AND、OR、XOR 与移位
  2. 设置、清除与翻转位
  3. 统计位数与最低位的置位
  4. 将位掩码用作微型集合
← 返回 Competitive Programming Academy