c++ - 将 64 位整数中的每隔一位与 32 位整数进行比较

Question

我正在考虑创建一个小的西洋跳棋解算器。首先，我会制作一个非常紧凑的棋盘表示，然后继续构建游戏树等。

一个标准的跳棋棋盘有 8 行和4 个功能列(跳棋只能沿对角线移动)。这给了我们 32 个位置!每个位置需要 3 位信息...king 位，color 位...所以 00 是 非 king black ，01是非王红，10是王黑，11 是王红色。这给了我们 64，这是一个很好的数字(长整数的精确大小)。

但是，每个棋子还需要一个额外的位...isOccupied 位，因为每个棋子的位置可以为空，也可以填充上述四种状态之一。我决定将 64 个状态放入一个 long 64 位整数，将 32 个占用状态放入一个 32 位整数。

现在我们有了一些背景知识，我有以下问题:我想轻松地说“这个棋盘上有多少红色跳棋？”嗯，还不错……我们的 64 位整数包含这样的数据:

king_color_king_color_king_color 所以 011001 意味着我们有红色，黑色 king，红色。

为了仅获取颜色信息，我们可以使用 01010101...01 的位掩码，即十六进制的 0x5555555555555555。这会将国王位清零，只留下颜色位。因此，对于 011001 示例，在与掩码进行与操作之后，我们得到 010001。如果我们计算位数 (popcount, bitcount)，我们会得到红色的数量...

啊，但是等等!这些颜色可能未“使用”。我们必须检查我们的 32 位 int 以查看是否正在使用给定的检查器!所以说我们有 011 作为我们占用的 32 整数......这意味着第一个检查器，上面的 01(红色非国王)......实际上没有被占用......它只是一个空方 block 。如果我们要将另一个检查器移到那里，我们可能需要也可能不需要更新那 2 个王色位。所以把它们放在一起

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然后简单地与 32 位运算得到 011 & 101 = 001。

那么正式地说，有没有一种方法可以将长度为 2X 的位串，通过仅取奇数位将其缩减为长度 X？我非常努力地避免循环、ifs 等，并且只使用逻辑(与、或、异或、否定等)。

当然，如果有另一种策略可以在给定我的 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 步中移动。

这种位算法有时被描述为“并行”。您可能有兴趣查看此 famous list . (它包括与这里发生的事情密切相关的交错。)

此类代码的标准免责声明是，它通常很难使用，因此除非确实存在性能问题，否则不应在严肃的项目中使用它(即便如此，请确保清楚代码应该做的，例如带有注释)。如果没有性能问题并且您仍然想使用位操作，那么循环解决方案可能仍然是首选，因为它更容易理解和使用。