在二进制字中找到1的最有效方法？

Question

我不确定会有什么样的东西会被称为(因此笨拙的标题),但我需要这样的东西来处理我正在做的事情.我无法用言语形容它,但我希望这张图能为我解释:

在这个例子中,当任意"索引"(例如5)之后的所有内容都被忽略时,获得"on-bits"数量的最快方法是什么？

Answer 1

首先input &= 0xfffffff8(或输入类型的等效项)清除最右边的三个位.然后从这里拿走你的选择.

Answer 2

除了已经说过的内容之外,我还想提醒你注意许多编译器都提供了一个内置的popcnt,它可能比手动更快(然后再说一次,也许不是,一定要测试它).它们的优点是可能编译为单个popcnt操作码,如果它在你的目标架构中可用(但我听说它们在回到库函数时做了愚蠢的慢事),而你很幸运,如果编译器检测到其中一个来自Sean的bithacks集合的算法(但它可能).

对于msvc,它是__popcnt(和变体),对于gcc它是__builtin_popcount(和变体),对于OpenCL(好吧你没有要求它,但为什么不把它扔进去)它是popcnt但你必须启用cl_amd_popcnt.