将 64 位整数中的每隔一位与 32 位整数进行比较
Comparing every other bit in a 64 bit integer to a 32 bit integer
我正在考虑创建一个小跳棋解算器的想法。首先，我会制作一个非常紧凑的跳棋棋盘表示，然后继续构建游戏树等。
一个标准的跳棋棋盘有 8 行 和 4 个功能列（跳棋只能沿对角线移动）。这给了我们 32 个位置！每个位置需要3位信息...king位，color位...所以00是非王黑，01是非王红，10是王黑，11是王红。这给了我们 64，这是一个很好的数字（长整数的精确大小）。
然而，每个棋子还需要一个额外的位... isOccupied 位，因为每个棋子位置可以为空，或填充上述四种状态之一。我决定把这64个状态放到一个long 64位的int中，把32个占用的状态放到一个32位的整数中。
所以现在我们有了一些背景知识，我有以下问题：我想轻松地说“这个棋盘上有多少红色跳棋？”还不错……我们的 64 位整数包含这样的数据：
king_color_king_color_king_color 所以 011001 意味着我们有红色，黑色国王，红色。
为了仅获取颜色信息，我们可以使用 01010101...01 的位掩码，即十六进制的 0x5555555555555555。这会将国王位清零，只留下颜色位。因此，对于 011001 示例，在与掩码进行与操作之后，我们得到 010001。如果我们计算位数 (popcount, bitcount)，我们会得到红色的数量...
啊，等等！这些颜色可能未“使用”。我们必须检查我们的 32 位 int 以查看是否正在使用给定的检查器！所以说我们有 011 作为我们占用的 32 整数......这意味着第一个检查器，上面的 01（红色非国王）......实际上没有被占用......它只是一个空方块。如果我们要将另一个检查器移到那里，我们可能需要也可能不需要更新那 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 位 AND 得到 011 & 101 = 001.
那么正式地说，有没有办法把长度为 2X 的位串，通过只取奇数位来减少到长度 X？我非常努力地避免循环、ifs 等，并且只使用逻辑（与、或、异或、否定等）。
或者当然，如果有另一种策略可以根据我的 32 位和 64 位字符串获得正确的红色计数。
谢谢！
编辑：
我提出的问题的解决方案在下面接受的答案中得到了优雅的解决，但对我的实际应用来说更好的解决方案是将 64 位表示拆分为两个 32。这为我节省了一堆操作来提取什么我需要。感谢 LukeG 和 Tehtmi 的帮助！我很高兴接触到这种位操作的新技术，“并行”。
我看不出有什么方法可以不使用循环来做到这一点。
编辑： tehtmi 证明我错了。虽然我仍然认为在这个答案末尾提出的 "alternative solution" 是解决手头问题的更好方法，但 tehtmi 提出了一个非常有趣的解决方案，如果您还没有，您应该向上滚动并投票。
我看到了两种解决方法。
第一个接近您想要实现的目标是：
uint32_t occupied;
uint64_t data;
uint32_t occupiedWithRed;
for (auto i = 0; i < 32; ++i) {
occupiedWithRed |= (data >> i) & occupied & (1 << i);
}
红色位置的计数将是 occupiedWithRed 中设置位的计数。
更简单（也可能更快）的方法是：
uint32_t occupied;
uint64_t data;
auto count = 0;
for (auto i = 0; i < 32; ++i) {
if ((data >> (2 * i)) & (occupied > i)) ++count;
}
或者，做一些完全不同的事情： 如评论中所述，如果您将数据分成 3 个不同的 32 位无符号整数，您的生活就会轻松很多。一种用于区分红色和黑色，一种用于区分空闲和占用，一种用于区分国王和无国王。这样你的任务会变得容易得多。这将是一个按位和计算汉明权重的问题。
与其收集偶数位或奇数位来与 32 个占用位进行比较，我宁愿采用另一种方式，将它们分配到一个 64 位整数中，这样它们就只出现在奇数位置上。此外，我会将它们移动到另一个 64 位整数中的偶数位置。
然后你可以很容易地将奇数位或偶数位的占用整数与位置信息整数中的偶数位或奇数位进行比较。
将数字中的每隔一位压缩成半长数字有点棘手，因为每一位都需要移动不同的量。然而，有一种聪明的方法可以做到这一点，它需要的操作比单独处理每个位要少。对于 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 步中移动。
这种位算法有时被描述为"parallel"。您可能有兴趣查看此 famous list。 （它包括与这里发生的事情密切相关的交错。）
此类代码的标准免责声明是，它通常很难使用，因此除非确实存在性能问题，否则不应在严肃的项目中使用它（即便如此，请确保它是明确的代码应该做什么，例如带有注释）。如果没有性能问题，你仍然想使用位操作，那么循环解决方案可能仍然是首选，因为它更容易理解和使用。
我正在考虑创建一个小跳棋解算器的想法。首先，我会制作一个非常紧凑的跳棋棋盘表示，然后继续构建游戏树等。
一个标准的跳棋棋盘有 8 行 和 4 个功能列（跳棋只能沿对角线移动）。这给了我们 32 个位置！每个位置需要3位信息...king位，color位...所以00是非王黑，01是非王红，10是王黑，11是王红。这给了我们 64，这是一个很好的数字（长整数的精确大小）。
然而，每个棋子还需要一个额外的位... isOccupied 位，因为每个棋子位置可以为空，或填充上述四种状态之一。我决定把这64个状态放到一个long 64位的int中，把32个占用的状态放到一个32位的整数中。
所以现在我们有了一些背景知识，我有以下问题：我想轻松地说“这个棋盘上有多少红色跳棋？”还不错……我们的 64 位整数包含这样的数据：
king_color_king_color_king_color 所以 011001 意味着我们有红色，黑色国王，红色。
为了仅获取颜色信息，我们可以使用 01010101...01 的位掩码，即十六进制的 0x5555555555555555。这会将国王位清零，只留下颜色位。因此，对于 011001 示例，在与掩码进行与操作之后，我们得到 010001。如果我们计算位数 (popcount, bitcount)，我们会得到红色的数量...
啊，等等！这些颜色可能未“使用”。我们必须检查我们的 32 位 int 以查看是否正在使用给定的检查器！所以说我们有 011 作为我们占用的 32 整数......这意味着第一个检查器，上面的 01（红色非国王）......实际上没有被占用......它只是一个空方块。如果我们要将另一个检查器移到那里，我们可能需要也可能不需要更新那 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 位 AND 得到 011 & 101 = 001.
那么正式地说，有没有办法把长度为 2X 的位串，通过只取奇数位来减少到长度 X？我非常努力地避免循环、ifs 等，并且只使用逻辑（与、或、异或、否定等）。
或者当然，如果有另一种策略可以根据我的 32 位和 64 位字符串获得正确的红色计数。 谢谢！
编辑：
我提出的问题的解决方案在下面接受的答案中得到了优雅的解决，但对我的实际应用来说更好的解决方案是将 64 位表示拆分为两个 32。这为我节省了一堆操作来提取什么我需要。感谢 LukeG 和 Tehtmi 的帮助！我很高兴接触到这种位操作的新技术，“并行”。
我看不出有什么方法可以不使用循环来做到这一点。
编辑： tehtmi 证明我错了。虽然我仍然认为在这个答案末尾提出的 "alternative solution" 是解决手头问题的更好方法，但 tehtmi 提出了一个非常有趣的解决方案，如果您还没有，您应该向上滚动并投票。
我看到了两种解决方法。
第一个接近您想要实现的目标是：
uint32_t occupied;
uint64_t data;
uint32_t occupiedWithRed;
for (auto i = 0; i < 32; ++i) {
occupiedWithRed |= (data >> i) & occupied & (1 << i);
}
红色位置的计数将是 occupiedWithRed 中设置位的计数。
更简单（也可能更快）的方法是：
uint32_t occupied;
uint64_t data;
auto count = 0;
for (auto i = 0; i < 32; ++i) {
if ((data >> (2 * i)) & (occupied > i)) ++count;
}
或者，做一些完全不同的事情： 如评论中所述，如果您将数据分成 3 个不同的 32 位无符号整数，您的生活就会轻松很多。一种用于区分红色和黑色，一种用于区分空闲和占用，一种用于区分国王和无国王。这样你的任务会变得容易得多。这将是一个按位和计算汉明权重的问题。
与其收集偶数位或奇数位来与 32 个占用位进行比较，我宁愿采用另一种方式，将它们分配到一个 64 位整数中，这样它们就只出现在奇数位置上。此外，我会将它们移动到另一个 64 位整数中的偶数位置。
然后你可以很容易地将奇数位或偶数位的占用整数与位置信息整数中的偶数位或奇数位进行比较。
将数字中的每隔一位压缩成半长数字有点棘手，因为每一位都需要移动不同的量。然而，有一种聪明的方法可以做到这一点，它需要的操作比单独处理每个位要少。对于 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 步中移动。
这种位算法有时被描述为"parallel"。您可能有兴趣查看此 famous list。 （它包括与这里发生的事情密切相关的交错。）
此类代码的标准免责声明是，它通常很难使用，因此除非确实存在性能问题，否则不应在严肃的项目中使用它（即便如此，请确保它是明确的代码应该做什么，例如带有注释）。如果没有性能问题，你仍然想使用位操作，那么循环解决方案可能仍然是首选，因为它更容易理解和使用。