c – 找到与另一个二进制模式匹配的所有2位值,然后求它们

发布时间：2020-12-16 03:36:05 所属栏目：百科来源：网络整理

导读：第一价值：我有一个二进制值,实际上是一个紧凑的2位值系列. (也就是说,二进制值中的每2位代表0,1,2或3.)因此,例如,3,2变为00110110.在这个二进制字符串中,我所关心的只是3(或者,我可以翻转位,只关心0,如果这使你的答案更容易).所有其他数字都无关紧要(因为

第一价值：

我有一个二进制值,实际上是一个紧凑的2位值系列. (也就是说,二进制值中的每2位代表0,1,2或3.)因此,例如,3,2变为00110110.在这个二进制字符串中,我所关心的只是3(或者,我可以翻转位,只关心0,如果这使你的答案更容易).所有其他数字都无关紧要(因为我们会稍微讨论一下).

第二价值：

我有第二个二进制值,它也是以相同方式表示的2位值的压缩系列.它与First Value具有相同的长度.

数学：

我希望第二个值中的2位数字的总和与第一个值中的3具有相同的位置.换句话说,如果我有：

First:  11000011
Second: 02222201

然后我的回答是“2”(我将第一个数字和最后一个数字从“第二个”加在一起,因为那些是唯一一个在第一个值中与“11”相匹配的数字.)

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

解决方法

当然.

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

现在创建一个掩码,它包含一个奇数位的’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位数字添加两轮.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!