c++ - 找到与另一个二进制模式匹配的所有 2 位值，然后将它们相加

Question

第一个值:

我有一个二进制值，它实际上是一个紧凑的 2 位值序列。 (也就是说，二进制值中的每 2 位代表 0、1、2 或 3。)因此，例如 0、3、1、2 变为 00110110。在这个二进制字符串中，我只关心 3(或者，我可以翻转位，只关心 0，如果这样可以让你的回答更容易的话)。所有其他数字都无关紧要(我们稍后会讨论原因)。

第二个值:

我有第二个二进制值，它也是一个压缩的 2 位值系列，以相同的方式表示。它与第一个值的长度相同。

数学:

我想要第二个值中与第一个值中的 3 具有相同位置的 2 位数字的总和。换句话说，如果我有:

First:  11000011
Second: 01111101

然后我的答案将是“2”(我将“第二”中的第一个数字和最后一个数字加在一起，因为它们是唯一在第一个值中匹配它们的“11”。)

我想在尽可能少的时钟周期内执行此操作(在 GPU 或 x86 架构上)。但是，我通常在寻找算法，而不是汇编程序解决方案。有没有比从每个数字中一次屏蔽掉两位并运行多个循环更快的方法？

Answer 1

当然可以。

 // the two numbers
 unsigned int a;
 unsigned int b;

现在从 a 中创建一个掩码，该掩码在奇数位置包含“1”位，前提是在相同位置有“11”结尾。

 unsigned int mask = a & (a >> 1) & 0x55555555;

展开它以获得“11”模式:

 mask = mask | (mask << 1);

所以现在如果 a 是 1101100011，掩码就是 1100000011。

然后用掩码遮住b:

 b = b & mask;

然后您可以从 b 并行执行(屏蔽)数字的加法:

 b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2);
 b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4);
 b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8);
 b = (b & 0x0000ffff) + ((b & 0xffff0000) >> 16);

对于 32 位数，和现在位于 b 的最低位。这是并行添加位域的常见模式。对于大于 32 位的数字，您可以为 64 位数字增加一轮，为 128 位数字增加两轮。