将64位整数中的每个其他位与32位整数进行比较

Question

我正在玩弄创建一个小的跳棋解算器的想法.首先,我将制作一个非常紧凑的跳棋板表示,然后继续构建游戏树等.

标准的检查板有8行,4个功能列(检查器只能移动对角线).这给了我们32个职位!每个位置需要的信息... 3位king位,和color位...所以00是无王黑,01是无王冲,10是王黑,11是王冲.这给了我们64这是一个很好的数字(长整数的精确大小).

但是,每个检查器还需要一个额外的位...该isOccupied位,因为每个检查器位置可以为空,或者填充上述四种状态之一.我决定采用64个状态并将它们放入一个长64位int,并将32个占用状态并将它们放入一个32位整数.

所以现在我们有一些背景知识,我有以下问题:我想轻易说"这块板上有多少个红色检查器？" 那不是那么糟糕......我们的64位整数包含这样的数据:

king_color_king_color_king_color所以011001意味着我们有红色,黑色的国王,红色.

为了得到颜色信息,我们可以使用01010101 ... 01的位掩码,它是十六进制的0x5555555555555555.这会将国王的位置归零,只留下颜色位.因此,在使用掩码进行AND运算后的011001示例中,我们有010001.如果我们计算位数(popcount,bitcount),我们得到红色数...

啊,等等!这些颜色可能不是"使用中".我们必须检查我们的32位int以查看是否正在使用给定的检查器!所以说我们已经为我们占用的32个整数设置了011 ...这意味着第一个检查器,上面的01(红色非国王)......实际上没有被占用...它只是一个空方块.如果我们要在那里移动另一个检查器,我们可能需要或不需要更新这两个王色位.所以把它们放在一起

32bit = 011
64bit = 011001

代表3个检查员职位......一个空的检查员之前是红色的,接着是黑色的国王,接着是红色.一旦我们在64位上执行010101掩码操作,我们得到:

64bitWithMask = 010001
32bit=011

天真的我们有2个红色...但我们实际上只有1个活动...我想要做的主要是采用64位字符串中的奇数位,并将它们与32位字符串中的每个位进行对比...即

1 AND 0, 0 AND 1, 1 AND 1 给我们001代表红色检查器的数量.

或者等效地,转换64bitWithMask为64bitWithMaskOddBits = 101 Then然后简单地用32位得到011 & 101 = 001.

那么形式上,有没有办法取一个长度为2X的字符串,并通过只取奇数位将其减少到长度X？我正在努力避免循环,ifs等,并且只使用逻辑(和,或,xor,否定等).

或者当然,如果有另一种策略可以根据我的32位和64位字符串获得正确的红色计数.谢谢!

编辑:

我提出的问题的解决方案在接受的答案中优雅地解决了,但是对于我的实际应用来说更好的解决方案是将64位表示分成两个32.这节省了一大堆操作来提取我需要的东西.感谢LukeG和Tehtmi的帮助!我很高兴接触到这种新的位操作技术,"并行".

Answer 1

将每个其他位从一个数字压缩为半长数字有点棘手,因为每个位需要移位不同的数量.但是,有一种聪明的方法可以比单独处理每个位需要更少的操作.对于64位,它看起来像这样(伪代码):

x = x & 0x5555555555555555
// or for the alternate bits: x = (x >> 1) & 0x5555555555555555
x = (x | (x >>  1)) & 0x3333333333333333
x = (x | (x >>  2)) & 0x0f0f0f0f0f0f0f0f
x = (x | (x >>  4)) & 0x00ff00ff00ff00ff
x = (x | (x >>  8)) & 0x0000ffff0000ffff
x = (x | (x >> 16)) & 0x00000000ffffffff

下面是一个32位数字(在初始掩码之后)每一步的位数发生的说明:

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p
00ab00cd00ef00gh00ij00kl00mn00op
0000abcd0000efgh0000ijkl0000mnop
00000000abcdefgh00000000ijklmnop
0000000000000000abcdefghijklmnop

例如,位g需要9向右移动,因此请查看两个幂的组件9 = 1 + 8.因此,g在>> 1步骤和>> 8步骤中移动.

这种比特算法有时被描述为"并行".您可能有兴趣查看这个着名的列表.(它包括与这里发生的事情密切相关的交错.)

这类代码的标准免责声明通常很难使用,因此它可能不应该用于严肃的项目,除非实际存在性能问题(即使这样,也要确保它清楚代码是什么做,例如评论).如果没有性能问题并且您仍然希望使用位操作,那么循环解决方案可能仍然是首选,因为它更容易理解和使用.