问题标签 [hammingweight]

使用 c 程序：

和编译器行（gcc 4.4 - Intel Xeon L3426）：

我没有得到内置的 popcnt 指令，而是编译器生成一个查找表并以这种方式计算 popcount。生成的二进制文件超过 8000 字节。（哎呀！）

非常感谢您的帮助。

一个很简单的问题：我有一个整数列表，例如，

现在我想要一个单独的列表，其中包含列表中每个整数的汉明权重（即二进制表示中 1 的位数）。这意味着上面整数列表的结果应如下所示：

任何人都知道我怎么能快速做到这一点？

我在 Visual C++ 2010 中使用 OpenCV 中的简要描述符来匹配两个图像中的点。

在关于简要描述符的论文中写道，可以加快速度：

“BRIEF 描述符使用汉明距离，这可以在现代 CPU 上以极快的速度完成，这些 CPU 通常提供特定指令来执行 XOR 或位计数操作，就像最新的 SSE 指令集一样。”

启用 SSE4.2 后应该会加快速度。我的问题只是我如何在 Visual C++ 中做到这一点？

另一种方法是选择另一个支持 SSE4 的编译器。例如英特尔的 ICC。这真的有必要吗？

假设我们有一个整数bitsize n=4;
我正在描述的问题是你将如何根据汉明权重和它的值将一个数字索引到一个数组位置bitsize。例如，位大小为 4 的具有 16 个元素的数组将/可能如下所示：

其中元素按其汉明权重（必要）分组并根据大小排序（非必要）。只要您可以使用例如 3(0011) 进行一些操作并取回索引 5、5(0101) -> 6 等，就不需要排序。

所有n位组合都将存在，并且不会有重复。例如 bitsize of3会有数组：

我最好有一个没有循环的解决方案。或任何讨论类似解决方案的论文。或者最后只是抛出任何关于如何去做的想法。

在处理 XKCD 愚人节的绞链散列冲突问题时，我遇到了这种奇怪的、快速的、乘法计算单词中设置位的方法：

为什么这样做/发生了什么？我们能否推广这种方法（例如，从问题中处理我们的 128 位值）？

另外，我不禁认为这与这个关于使用聪明的幻数移动位的问题有关。

我正在 Intel Xeon® Phi® 上实现超快速 popcount，因为它是各种生物信息学软件的性能热点。

我已经实现了五段代码，

可以从https://www.dropbox.com/sh/b3sfqps19wa2oi4/iFQ9wQ1NTg下载支持 OpenMP 的代码总结

该代码是使用 Intel C/C++ Compiler XE 13 使用命令编译的：

代码在协处理器（61 个内核）上以“122 个线程”本地运行，线程亲和性为“平衡”，使用导出：

我正在使用Xeon Phi SE10p，B1 stepping，CentOS6.4在28兆的垃圾（由rand()填充）上测试并迭代10000次，性能如下：

“scalar_popcountu”和“scalar_popcountlu”分别使用“_mm_countbits_32”和“_mm_countbits_64”内在函数，它们利用标量“popcnt”指令。设置“#pragma vector always”要求编译器将负载和总和向量化为 16 个无符号整数或 8 个无符号长整数，尽管 popcount 本身仍然是一个标量指令。

vpu_popcount1 的实现类似于 SSSE3 popcount 实现http://wm.ite.pl/articles/sse-popcount.html。但是，1) Xeon Phi 不支持对整数的打包字节操作（最小值是双字，也就是 32 位）和 2) 它不实现“绝对差的打包和”指令（如 SSSE3 中的 _mm_sad_epu8），因此减少添加是由“vpermf32x4”、“vpaddd”和“movslq”四组组合执行的。因此，该实现生成的指令比原始 SSSE3 版本多得多。

vpu_popcount2 的实现类似于 SSE2 popcount 的实现（可以参考《Hacker's Delight》）。该实现生成的指令比 vpu_popcount1 少，速度快 30% 左右。然而，繁琐的“减加”依然无法避免。

vpu_popcount3 的实现非常特定于 Xeon Phi。混合使用向量和标量操作，它比 vpu_popcount2 快约 15%（在我的实现中，向量操作中的标量操作的穿插是休闲的，可以根据编译器生成的汇编代码重新排列标量操作，但预期的改进就我而言是有限的）。改进基于以下观察：1) Xeon Phi 是按顺序调度，2) 每个时钟周期可以发出两条标量指令或“1 个向量+1 个标量”指令。我已将展开从 8 减少到 4，以避免寄存器文件饱和。

每个函数中提前从内存到 L2 8 循环和从 L2 到 L1 1 循环的显式预取使 L1 命中率从 0.38 增加到 0.994。

展开确实将性能提高了约 15%。这是反直觉的，因为 Xeon Phi 是按顺序调度的。但是 unroll 使 icc 编译器能够进行尽可能多的编译时间调度。

我们有更多的技术来提高性能吗？

来自 Brian Nickerson 的两段更快的代码，

vpu_popcount3_revised：

vpu_popcount5：

我有一个像这样的表声明

和价值观

现在我想选择条形的 id 和人口计数（也称为汉明权重）。

在我的例子中

会回来

我必须做什么才能获得人口数量？

^{请不要回答如何在客户端执行此操作。我希望该解决方案也可用于 WHERE、ORDER BY、HAVING 等。}

我应该计算 __m128i 寄存器的设置位数。特别是，我应该使用以下方法编写两个能够计算寄存器位数的函数。

1. 寄存器的设置位总数。
2. 寄存器每个字节的设置位数。

是否存在可以全部或部分执行上述操作的内在功能？

我想比较两个数字以确定必须翻转的位数才能使它们相等。

例如，5 和 6 需要 2 位翻转。

我可以手动执行此操作，但想编写一个 Lua 函数来为我执行此操作，例如：

我只对将八进制与八进制进行比较感兴趣（呵呵），因此该函数将返回值 0-3。有没有一种比使用桌子更好的有效/优雅的方法来做到这一点？

我看过这段代码，它计算的位数等于132 位整数，我注意到它的性能优于__builtin_popcount但我无法理解它的工作方式。

有人可以详细解释这段代码是如何工作的吗？