这是我在!! Con 2019上的演讲的伪解码。当今使用的大多数处理器体系结构都有称为
popcount指令，
popcount是“人口数”的缩写。 她执行以下操作：计算机器字中设置的位数。 例如（为简单起见，我们采用8位字），
popcount(00100110)为3，
popcount(01100000)为2。
就像我一样，这可能会让您大吃一惊，但这就是她所做的！ 似乎不是很有帮助，对不对？
我认为这是对某些超专业用例的最新补充，但实际上至少从1961年开始，它就已出现在处理器体系结构中：
那到底是怎么回事？
NSA指令
popcount也被称为“ NSA指令”，
popcount一个
非常有趣的线程讨论了它在密码学中的用法。 有传言说，它最初是应NSA的要求添加到CPU指令集中的。 如
该归档邮件线程中所述 ：
将每批速度更快的CDC汽车中的一辆发送给“好客户”几乎是一种传统-一辆未知的卡车到了，再也没有听到过。
一个伟大的传说，但是为什么他们要使用它呢？
内容的一种度量是
Hamming的weight ，它是字符串中非零字符的数量。 对于二进制字符串，这是
popcount ！
如此处
所述 ，NSA需要对截获的消息进行加密分析，并且由于CDC 6000使用60位单词，因此一个单词足以存储感兴趣的大多数字母。 他们能够：
- 将消息分成几行
- 为字符串中的每个唯一字符设置一个位
- 使用
popcount计算不同字符的数量
- 将计数器用作哈希以进行进一步的密码分析
奇怪的是，
popcount似乎在1970年代中期至2000年代中期的指令集中消失了，因此返回值应该用加密应用程序以外的方式解释。 它还有什么用？
错误修复
汉明权重的概念与汉
明距离有关，
汉明距离是相同长度的两条线之间不同位置的数量。 对于两个二进制字符串
x和
y ，这只是
popcount之后的
popcount 。 例如：
00100110
01100000 ^
--------
01000110
popcount（01000110）= 3
在电信应用中，这有助于计算信号距离，在已知距离处沿导线传输一个已知字，并对改变的位数进行计数以估算传输错误。
然后我们可以设计合适的
纠错码 。 例如，如果传输必须承受两个修改位，则代码字的汉明距离应相差至少5个。
二元卷积神经网络
现在完全不同了：二进制卷积神经网络！ 但是首先，这是什么？
- 二进制表示与32位浮点值不同，我们仅使用值+1（编码为1）和-1（编码为0）的矩阵。
- 卷积是否意味着矩阵相乘？
- 神经网络是受动物大脑启发的系统（我在这里游泳了一点）。
因此，我们必须执行二进制矩阵的乘法。 但是二进制矩阵有什么特别之处？
常规矩阵乘以32位值非常适合具有强大CPU和GPU的台式计算机，但是我们越来越经常希望在小型和简单的设备（例如智能手机，路由器，智能手表等）上做有用的工作。我们可以对它们进行分解二进制矩阵的层可以使用更复杂的矩阵，并且使用它们和存储它们更加容易，即使层数增加，我们也可以从中受益。
这就是
popcount发挥作用的地方。 它用于计算两个二进制矩阵的标量积：
a = xnor（x，y）
b =弹出数（a）
c = len（a）
点（x，y）= 2×b-c
有关更多详细信息，请参见
此处和
此处 。
国际象棋编程
许多国际象棋程序都以位
板表示形式存储数据，可以方便地将其放入64位字中。
Population Count操作用于此视图下的有意义的操作，例如计算图形的
移动性 。
分子指纹
这也与汉明距离有关：以某种方式对分子进行散列和比较（使用
popcount ）以确定它们之间的相似程度。 有关更多详细信息，请参见
此处 。
哈希数组映射尝试（HAMT）
这是我第一次了解
popcount ！ HAMT是一种数据结构（
最初由Phil Bagwell创建 ），可以在每个trie节点上的数组中存储非常多的值（通常为32或64）。 但是，每次为32或64个元素的数组分配内存可能非常浪费，尤其是在该数组实际上仅包含几个元素的情况下。 解决方案是添加一个位掩码，其中设置的位数与数组中元素的数量相对应，这允许数组根据需要增长和收缩。 可以使用
popcount有效地完成给定元素的索引计算。 在有关实现HAMT结构的
博客文章中 ，您可以了解有关它们如何工作的更多信息。
压缩数据结构
这是一个令人兴奋的新研究领域，其重点是如何在最小的空间内存储数据而又不拆包以完成有用的工作。 一种方法是根据可以在两个操作中请求的位的数组（位向量）进行思考：
rank(i)计算直到位向量中第i个索引为止的位数
select(i)查找设置第i位的索引
为了使这些操作在大位向量上高效，在两种情况下都需要建立索引并有效使用它，这两种情况都涉及
popcount 。 这是RRR指数的良好概述。 而且，据我所知，最先进的现代方法
在未压缩位序列上的空间高效，高性能等级和选择结构一文中进行了介绍 。
编译器优化
popcount变得如此广泛，以至于
GCC和
Clang都能够检测到它并用内置指令替换它。 想象一下这个Clippy：“哦，我看到您正在尝试实现
popcount ，让我出去为您修复它！” 相应的LLVM代码在
此处 。 Daniel Lemyr引用它作为现代编译器令人惊叹的头脑的一个例子。
结论
尽管它仍然有点不寻常的CPU指令，但
popcount指令在其历史的
popcount在神秘之中，开始在
popcount使用。 我喜欢它连接计算机科学这些不同领域的方式，并且我想知道还有多少其他这种奇怪的指令。 如果您有自己的最爱，我想听听她的消息！