问题标签 [hammingweight]

代表数字 7 的 8 位如下所示：

设置了三位。

确定 32 位整数中设置位数的算法是什么？

我有一组五个布尔值。如果其中一个以上是真的，我想执行一个特定的功能。你能想到的最优雅的方式是什么，它可以让我在一个 if() 语句中检查这个条件？目标语言是 C#，但我也对其他语言的解决方案感兴趣（只要我们不讨论特定的内置函数）。

一个有趣的选择是将布尔值存储在一个字节中，进行右移并与原始字节进行比较。但是这需要将单独的布尔值转换为字节（通过bitArray if(myByte && (myByte >> 1))？），这似乎有点（双关语）笨拙...... [编辑]对不起，应该是 if(myByte & (myByte - 1)) [/编辑]

注意：这当然非常接近经典的“人口计数”、“横向加法”或“汉明权重”编程问题——但并不完全相同。我不需要知道设置了多少位，只要它不止一个。我希望有一种更简单的方法来实现这一点。

我需要 C 代码来返回 C 中 unsigned char 中 1 的数量。如果不明显，我需要解释为什么它可以工作。我发现了很多 32 位数字的代码，但对于 unsigned char 却没有多少。

给定要解释为位字符串的 MATLAB uint32，计算字符串中有多少非零位的有效且简洁的方法是什么？

我有一个可行的、幼稚的方法来循环这些位，但这对我的需要来说太慢了。（使用 std::bitset count() 的 C++ 实现几乎立即运行）。

我发现了一个非常不错的页面，列出了各种位计数技术，但我希望有一种简单的 MATLAB 式方法。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

更新#1

刚刚实现了 Brian Kernighan 算法如下：

性能仍然很糟糕，仅计算 4096^2 权重计算需要超过 10 秒。我的 C++ 代码使用 std::bitset 中的 count() 可以在亚秒时间内完成。

更新#2

这是迄今为止我尝试过的技术的运行时间表。当我得到更多的想法/建议时，我会更新它。

评论：MATLAB 中的 dec2bin() 函数似乎实现得很差。它运行非常缓慢。

评论：“Naive bitget loop”算法实现如下：

评论： Scheiner 算法的循环展开版本如下所示：

我有一个 32 位数字，想知道有多少位是 1。

我在想这个伪代码：

有没有更有效的方法？

我在 x86 处理器上使用 NASM。

（我刚开始使用汇编程序，所以请不要告诉我使用外部库中的代码，因为我什至不知道如何包含它们；））

（我刚刚发现如何计算 32 位整数中的设置位数？其中也包含我的解决方案。发布了其他解决方案，但不幸的是我似乎无法弄清楚，我将如何在汇编程序中编写它们）

我正在寻找对 512 或更多字节的大缓冲区进行 popcount 的最快方法。我可以保证任何所需的对齐，并且缓冲区大小始终是 2 的幂。缓冲区对应于块分配，因此通常这些位要么全部设置，要么未设置，或者大部分设置有利于缓冲区的“左侧”，与偶尔的洞。

我考虑过的一些解决方案是：

• 海合会__builtin_popcount
• 位片popcount_24words
• 计数位设置，Brian Kernighan 的方式

我对最快的解决方案感兴趣，它必须在属于 core2 或更新版本的 32 位 x86 芯片组上工作。SSE 和 SIMD 非常有趣。我将在以下四核 CPU 上进行测试：

我想计算设置的二进制数中的位数。例如，用户输入数字 97，即二进制 01100001。该程序应该告诉我使用 MIPS ISA 设置了 3 位。

我能够在 C 中实现这一点，但我不知道如何使用汇编代码来实现它。

我有一个程序正在对 Long.bitCount() 进行大量调用，如此之多以至于它在一个 CPU 内核上占用了 33% 的周期。有没有比 Sun JDK 版本更快的方法来实现它？

我试过了：

• 这个算法（我认为这正是JDK的实现方式）
• ^{2 8}到 2 ²²之间的各种大小的查找表（一次查看几位并添加结果）

但是我没有比使用手动展开循环（大约 27% 的 CPU）的 2 ¹⁶条目查找表做得更好的了。
这还能如何针对 Java 进行优化？

注意：这个问题是关于特定于 Java 的优化，但是这个类似的（与语言无关的）问题还有许多其他算法。

是否有类似于 JavaInteger.bitCount(int)或Long.bitCount(long).NET Framework 中任何地方的方法？

（对于那些不熟悉这些 Java 方法的人）这也被称为：

• 汉明重量
• 人口计数（通常POPCNT在硬件中实现时调用。）

虽然在 网上可以找到很多 实现，但我想知道是否有标准库实现。

我知道这不在BitArray,UInt32或中BitConverter，但也许在某个地方隐藏了一个版本，例如在加密函数中。

我正在寻找一种快速的方法来计算 BINARY(1024) 字段的汉明权重/人口计数/“1 位的数量”。MySQL 有一个 BIT_COUNT 函数可以做类似的事情。我在 T-SQL 中找不到类似的函数？

或者您会建议将二进制数据存储在另一种类型的字段中吗？

如果你不知道我在说什么，这里有一篇关于汉明权重的维基百科文章。