在二进制中寻找1的最有效方法是什么？

Question

我不确定类似这样的东西应该叫什么名字（因此标题有些拙劣），但我需要这样的东西来完成我的项目。我用言语无法很好地描述它，但我希望这个图示可以为我解释：

在这个例子中，当忽略任意“索引”（例如5）后的所有内容时，“on-bits”的数量（即“3”）最快的方式是什么？

- Anne Quinn

---

简单的屏蔽操作可以用于“被忽略”的部分。参考链接为：http://graphics.stanford.edu/~seander/bithacks.html - Mat

@Mat - ...哦，傻了！我不确定为什么我认为那必须在找到位之后发生。我想这只剩下找到开启的位了。 - Anne Quinn

我想知道为什么这个操作是你的程序瓶颈... - lhf

@lhf - 从来没有这么说过！我想，如果我要问如何做某事，最好还是问最好的方法。 :P - Anne Quinn

有关变量截止索引，请参见什么是计算某个位置或更低位设置位的有效方法？。（这对于位具有特殊含义，甚至更加偏爱移位。） - Peter Cordes

Answer 1

除了已经说过的内容，我想提醒您许多编译器提供内置的popcnt功能，可能比手动计算更快（当然，也可能不是，请务必测试）。它们的优点是如果目标架构中有可用的popcnt操作码，则可能编译为单个popcnt操作码（但我听说当回退到库函数时，它们会做一些愚蠢缓慢的事情），而如果编译器检测到Sean的bithacks集合中的任何算法，则您将非常幸运（但可能性很小）。

对于msvc，它是__popcnt（和变体），对于gcc，它是__builtin_popcount（和变体），对于OpenCL（好吧，您没有要求，但为什么不加入呢？）它是popcnt，但必须启用cl_amd_popcnt。

- harold

---

一旦我有足够大的测试来进行适当的分析，我总是可以将其放入#ifdef块中并与我编写的内容进行比较。谢谢！ - Anne Quinn

Answer 2

首先做 input &= 0xfffffff8（或者根据您的输入类型选择相应的等价方法）以清除最右边的三位。然后从这里任选一种方法。

- Jon

---

我太蠢了，没有在尝试查找已设置的位之前屏蔽位。这会使事情变得更容易。感谢您的文章。可能最终会使用表查找。 - Anne Quinn

Answer 3

以下是类似的内容：

int
countOnes( unsigned value, int top )
{
    assert( top >= 0 && opt < CHAR_BIT * sizeof( unsigned ) );
    value &= ~(~0 << top);
    int results = 0;
    while ( value != 0 ) {
        ++ results;
        value &= value - 1;
    }
    return results;
}

这取决于一个有点难以理解的事实，即i & (i - 1)会重置低位的比特位。

- James Kanze

---

这是一个很棒的属性，考虑一下。而且它肯定有效！如果可以的话，我会使用类似这样的东西来构建查找表，并从中获取数据。 - Anne Quinn

如果你只需要计算一个字节以内的数值，那么查找表显然是最好的选择。（事实上，如果你需要计算更多的数值，将该值视为字节数组，并从查找表中获取的值相加仍然是一个非常好的解决方案。） - James Kanze

实际上，我可能需要一个更长的数据类型。我将同时使用查找表和不使用查找表来完成它，并在以后对其进行优化。 - Anne Quinn

Answer 4

查找表可以在常数时间内提供这些信息。

- lhf

---

完全没有想到这一点。而且只有256种排列方式。谢谢！ - Anne Quinn

查找表对于字节来说还好，但对于像 int 这样的类型，它变得有点笨重。（而且你仍然需要掩码来修剪顶部不需要的位。） - James Kanze

请注意，查找表可能效率低下（缓存未命中），并且不适合通过SIMD进行向量化。当然，如果性能不是问题，那就没关系了。 - Paul R

@PaulR，你可以使用SIMD替换查找表，pshufb非常棒。只需要2个pshufb，因为它只是一个16字节的LUT。http://wm.ite.pl/articles/sse-popcount.html - harold

@harold：是的 - 这实际上是两种有用技术的组合：（i）将问题分解为两个4位人口统计信息，并且（ii）使用排列指令对每个nybble执行查找。 - Paul R