算法与计算机科学vaibhavsagar.com
Popcount CPU 指令
Popcount CPU instruction
2019 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章介绍 popcount——用一条指令统计机器字中 1 的个数的 CPU 指令，回顾了它从 IBM Stretch 时代以来的历史渊源，以及它与 NSA 情报工作之间流传已久的传闻。看似冷门的位操作，背后是硬件设计、性能优化与计算史的交汇。
为什么经久不衰：一条小指令串起了冷战密码学、指令集演化和真实的性能收益，每隔几年就有人重新发现它的妙用，至今仍是位操作优化的必修课。
HN 评论精选
图灵早在 1940 年代就为 Ferranti Mark 1 争取到了 popcount 指令，比 IBM Stretch 更早。
几年前我读了 Andrew Hodges 的《艾伦·图灵传》，里面藏着早期计算史的珍宝：二战后图灵参与 ACE 电子计算机项目，因官僚拖累进展缓慢，后来去了曼彻斯特。据书中记载，他仍以外部顾问身份为后来成为 GCHQ 的 G.C. & C.S. 工作，说服对方购买一台 Ferranti Mark 1（大概用于密码分析），并坚持要求加入一个"横向加法器"，使机器能用一条指令统计一个字中置位的数量——也就是 popcount。这比文章提到的 IBM Stretch 还要早。
st_goliath查看英文原文
Some years back, I got myself a copy of Andrew Hodges "Alan Turing - The Enigma", a biography and IMO generally a good read, but also with some gems regarding very early computing history in it. Specifically, after WWII, Turing worked on the ACE 1 (later reduced to Pilot ACE) project to build an electronic computer, which didn't really progress due to management and bureaucracy overhead. He eventually went to Manchester, once they got their Manchester Mark 1 off the ground, which they tried to commercialize as "Ferranti Mark 1" (https://en.wikipedia.org/wiki/Ferranti_Mark_1). While employed for the University, Turing IIRC continued to work as an external consultant for whatever became of G.C. & C.S. on the side. According to the book, he convinced them to buy such a machine (presumably for crypt-analysis?) and, on the Manchester side of things, insisted on some modifications to be made, including a "horizontal adder", so it could count the number of bits set in a word with a single instruction, i.e. a popcount instruction. This would pre-date the IBM Stretch mentioned in the article.
老牌架构师的共识：popcount 进指令集并非 NSA 要求，真正原因早于 NSA 采购。
1992 年那场 comp.arch 新闻组讨论（其中有 Animats 一条非常精彩的评论）的共识是：popcount 进入各种指令集通常并非应 NSA 的要求——了解这些架构内情的人知道真正的原因，而且那发生在 NSA 采购之前。
tptacek查看英文原文
The consensus on the 1992 thread (including a really great comment from 'Animats) seems to be that `popcount` was generally not added to architectures at NSA's request --- that people familiar with those archs knew the actual reason `popcount` wound up in the ISA, and it preceded NSA purchases. https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC7Xhr8J
用 bitset 存邻接矩阵，popcount 可以极快地求出顶点度数和公共邻居。
楼主没提到的一个用途是图分析：可以用 std::bitset<N> 数组把最多 N 个顶点的图的邻接矩阵存进 N² 个比特里，而 std::bitset::count 底层正是 popcount。这让很多图操作即使 N 相当大也快得惊人——graph[i].count() 直接得到顶点的度数，(graph[i] & graph[j]).count() 得到与 i、j 都相邻的顶点数。
monday_查看英文原文
One way popcount is useful not mentioned in the OP is in the graph analysis. For example, you can use the following std::bitset<N>* graph = new std::bitset<N> [N]; to store the adjacency matrix for a graph with up to N vertices in N^2 bits of memory. The nice thing is that std::bitset::count uses popcount to compute the number of bits set to one. This makes some graph operations extremely fast even for a pretty large N. For example, graph[i].count() will produce a degree of a vertex and (graph[i] & graph[j]).count() will produce a number of vertices adjacent to both i and j.
.NET Core 3 已内置 popcount 支持，Kestrel 用它来加速 HTTP 头的识别。
.NET Core 3（当时在预览，9 月 23 日发布）在 BitOperations 类中加入了 popcount 支持。潜在用例很多，早期讨论之一就是快速扫描已知 HTTP 头，Kestrel 服务器里就有实际应用。如果你实在睡不着，还可以去看看 2015 年就开始的那场讨论。
jongalloway2查看英文原文
.NET Core 3 (in preview, due out Sep 23) includes support for popcount as part of the BitOperations class: https://docs.microsoft.com/en-us/dotnet/api/system.numerics.bitoperations. There's a recent post describing hardware intrinsics in .NET Core: https://devblogs.microsoft.com/dotnet/hardware-intrinsics-in-net-core/ There are a lot of potential use cases, but one of the early discussions was around quickly scanning for known HTTP headers. You can see that in use here: https://github.com/aspnet/AspNetCore/blob/caa910ceeba5f2b2c02c47a23ead0ca31caea6f0/src/Servers/Kestrel/shared/KnownHeaders.cs#L646 If you really need help falling asleep, here's the discussion going back to 2015: https://github.com/dotnet/corefx/issues/2209 Disclaimers: Microsoft employee, Nazgûl
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选