我在另一个问题的答案中看到了一种有趣的技术，并且想更好地理解它。
我们得到一个无符号的 64 位整数，我们对以下位感兴趣：
1.......2.......3.......4.......5.......6.......7.......8.......
具体来说，我们希望将它们移动到前八位，如下所示：
12345678........................................................
我们不关心由 指示的位的值.，也不必保留它们。
解决方案是屏蔽掉不需要的位，并将结果乘以0x2040810204081. 事实证明，这可以解决问题。
这种方法有多普遍？这种技术可以用来提取比特的任何子集吗？如果不是，如何确定该方法是否适用于特定的一组位？
最后，如何找到（a？）正确的乘数来提取给定的位？
非常有趣的问题，巧妙的把戏。
让我们看一个处理单个字节的简单示例。为简单起见，使用无符号 8 位。想象一下你的号码是xxaxxbxx你想要ab000000的。
该解决方案包括两个步骤：位掩码，然后是乘法。位掩码是一个简单的 AND 操作，将不感兴趣的位变为零。在上述情况下，您的掩码将是00100100和结果00a00b00。
现在最困难的部分：把它变成ab.......
乘法是一堆移位和加法运算。关键是允许溢出“移走”我们不需要的位并将我们想要的位放在正确的位置。
乘以 4( 00000100) 会将所有内容左移 2 并得到a00b0000。为了让ba 向上移动，我们需要乘以 1（将 a 保持在正确的位置）+ 4（将 b 向上移动）。这个和是 5，再加上前面的 4，我们得到一个幻数 20，或00010100。原来是00a00b00蒙版后的；乘法给出：
000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......
通过这种方法，您可以扩展到更大的数字和更多位。
你问的一个问题是“这可以用任意数量的比特来完成吗？” 我认为答案是“不”，除非您允许多次屏蔽操作或多次乘法。问题是“碰撞”的问题——例如上面问题中的“流浪b”。想象一下，我们需要对像xaxxbxxcx. 按照前面的方法，你会认为我们需要 {x 2, x {1 + 4 + 16}} = x 42（哦——所有问题的答案！）。结果：
00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......
如您所见，它仍然有效，但“只是”。这里的关键是我们想要的位之间有“足够的空间”，我们可以把所有东西都挤起来。我不能在 c 之后立即添加第四位 d，因为我会得到 c+d 的实例，位可能携带，...
因此，如果没有正式的证据，我将回答您问题中更有趣的部分如下：“不，这不适用于任何位数。要提取 N 位，您需要在您想要的位之间有 (N-1) 个空格提取，或有额外的掩码乘法步骤。”
对于“位之间必须有 (N-1) 个零”规则，我能想到的唯一例外是：如果要提取原始中彼此相邻的两个位，并且要将它们保留在同样的顺序，那么你仍然可以做到。并且出于 (N-1) 规则的目的，它们计为两位。
还有另一种见解 - 受到下面@Ternary 答案的启发（请参阅我的评论）。对于每个有趣的位，您只需要它右侧的零，因为您需要空间用于需要去那里的位。而且，它需要的左侧位数与左侧的结果位数一样多。因此，如果位 b 最终位于 n 的位置 m，那么它的左侧需要有 m-1 个零，右侧需要有 nm 个零。特别是当位在原始编号中的顺序与重新排序后的顺序不同时，这是对原始标准的重要改进。这意味着，例如，一个 16 位字
a...e.b...d..c..
可以转成
abcde...........
即使 e 和 b 之间只有一个空格，d 和 c 之间只有两个空格，其他空格之间只有三个空格。N-1怎么了？？在这种情况下，a...e变成“一个块”——它们乘以 1 以在正确的位置结束，因此“我们免费获得了 e”。b 和 d 也是如此（b 需要右边三个空格，d 需要左边三个空格）。所以当我们计算幻数时，我们发现有重复：
a: << 0 ( x 1 )
b: << 5 ( x 32 )
c: << 11 ( x 2048 )
d: << 5 ( x 32 ) !! duplicate
e: << 0 ( x 1 ) !! duplicate
显然，如果您希望这些数字以不同的顺序排列，则必须将它们间隔得更远。我们可以重新制定(N-1)规则：“如果位之间至少有 (N-1) 个空格，它将始终有效；或者，如果最终结果中的位顺序已知，那么如果位 b 最终位于n，它的左边需要有 m-1 个零，右边需要有 nm 个零。”
@Ternary 指出这条规则不太适用，因为可能有一个进位从位添加“就在目标区域的右侧” - 即，当我们正在寻找的位都是 1 时。继续我上面给出的例子，在一个 16 位字中包含五个紧凑的位：如果我们从
a...e.b...d..c..
为简单起见，我将命名位位置ABCDEFGHIJKLMNOP
我们要做的数学是
ABCDEFGHIJKLMNOP
a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00
到目前为止，我们认为任何低于abcde(positions ABCDE) 的东西都无关紧要，但实际上，正如@Ternary 指出的那样，如果b=1, c=1, d=1then (b+c)in positionG会导致 bit 进位到 position F，这意味着(d+1)in positionF会进位E- 而我们的结果被宠坏了。请注意，感兴趣的最低有效位（c在此示例中）右侧的空间无关紧要，因为乘法将导致在最低有效位之外用零填充。
所以我们需要修改我们的 (m-1)/(nm) 规则。如果有不止一个位在右侧有“恰好 (nm) 个未使用的位（不包括模式中的最后一位 - 上例中的“c”），那么我们需要加强规则 - 我们必须反复这样做！
我们不仅要查看满足 (nm) 标准的位数，还要查看处于 (n-m+1) 处的位数等。让我们称它们的数为 Q0（精确n-m到下一位），Q1 ( n-m+1)，直到 Q(N-1) (n-1)。然后我们冒险携带如果
Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
...
如果你看这个，你可以看到如果你写一个简单的数学表达式
W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)
结果是W > 2 * N，那么您需要将 RHS 标准增加一位(n-m+1)。此时，操作是安全的W < 4；如果这不起作用，请再增加一个标准，等等。
我认为遵循上述内容将使您对答案有很长的路要走...
确实非常有趣的问题。我用我的两分钱插话，也就是说，如果你能设法用位向量理论的一阶逻辑来陈述这样的问题，那么定理证明器就是你的朋友，并且可能为你提供非常快的回答您的问题。让我们将所提出的问题重新表述为定理：
“存在一些 64 位常量 'mask' 和 'multiplicand' 这样，对于所有 64 位位向量 x，在表达式 y = (x & mask) * multiplicand 中，我们有 y.63 == x.63 , y.62 == x.55, y.61 == x.47 等"
如果这句话实际上是一个定理，那么常数 'mask' 和 'multiplicand' 的某些值确实满足这个性质。因此，让我们用定理证明者可以理解的东西来表达这一点，即 SMT-LIB 2 输入：
(set-logic BV)
(declare-const mask (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))
(assert
(forall ((x (_ BitVec 64)))
(let ((y (bvmul (bvand mask x) multiplicand)))
(and
(= ((_ extract 63 63) x) ((_ extract 63 63) y))
(= ((_ extract 55 55) x) ((_ extract 62 62) y))
(= ((_ extract 47 47) x) ((_ extract 61 61) y))
(= ((_ extract 39 39) x) ((_ extract 60 60) y))
(= ((_ extract 31 31) x) ((_ extract 59 59) y))
(= ((_ extract 23 23) x) ((_ extract 58 58) y))
(= ((_ extract 15 15) x) ((_ extract 57 57) y))
(= ((_ extract 7 7) x) ((_ extract 56 56) y))
)
)
)
)
(check-sat)
(get-model)
现在让我们问定理证明者 Z3 这是否是一个定理：
z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2
结果是：
sat
(model
(define-fun mask () (_ BitVec 64)
#x8080808080808080)
(define-fun multiplicand () (_ BitVec 64)
#x0002040810204081)
)
答对了！它在 0.06 秒内重现了原始帖子中给出的结果。
从更一般的角度来看，我们可以将其视为一阶程序综合问题的一个实例，这是一个新兴的研究领域，很少有论文发表。搜索"program synthesis" filetype:pdf应该让你开始。
乘法器中的每个 1 位用于将其中一个位复制到其正确位置：
1已经在正确的位置，所以乘以0x0000000000000001.2必须向左移动 7 位，所以我们乘以0x0000000000000080（设置了第 7 位）。3必须向左移动 14 位位置，所以我们乘以0x0000000000000400（设置了第 14 位）。8必须向左移动 49 位位置，因此我们乘以0x0002000000000000（设置了第 49 位）。乘数是各个位的乘数之和。
这只起作用是因为要收集的位不是靠得太近，因此在我们的方案中不属于一起的位的乘法要么超出 64 位，要么位于较低的无关部分。
请注意，原始数字中的其他位必须是0。这可以通过使用 AND 操作屏蔽它们来实现。
（我以前从未见过。这个技巧很棒！）
我将对 Floris 的断言进行一些扩展，即在提取n位时，您需要n-1在任何非连续位之间留出空间：
我最初的想法（我们将在一分钟内看到这如何不起作用）是你可以做得更好：如果你想提取n位，i如果你有任何人（非- 在前面的位或后面的位中与 bit i)连续。i-1n-i
我举几个例子来说明：
...a..b...c...有效（之后的 2 位中没有人，a之前的位和之后的位b中没有人，之前的 2 位中没有人c）：
a00b000c
+ 0b000c00
+ 00c00000
= abc.....
...a.b....c...失败是因为b在 2 位之后a（当我们 shift 时被拉到其他人的位置a）：
a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....
...a...b.c...失败，因为bis 在前面的 2 位中c（当我们 shift 时被推到其他人的位置c）：
a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....
...a...bc...d...有效，因为连续的位一起移位：
a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000
但是我们有一个问题。如果我们使用n-i而不是，n-1我们可能会遇到以下情况：如果我们在我们关心的部分之外发生碰撞，我们会在最后屏蔽掉一些东西，但其进位位最终会干扰重要的未屏蔽范围? （注意：当我们移动第th 位时n-1，通过确保我们的未屏蔽范围之后的位是清晰的，要求确保不会发生这种情况）i-1i
...a...b..c...d...进位的潜在故障c在n-1after中b，但满足n-i标准：
a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......
那么我们为什么不回到那个“n-1空间位”的要求呢？
因为我们可以做得更好：
...a....b..c...d.. 未通过“n-1位空间”测试，但适用于我们的位提取技巧：
+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......
我想不出一个好的方法来描述这些在重要位之间没有空间的字段，但n-1仍然适用于我们的操作。但是，由于我们提前知道我们感兴趣的位，我们可以检查我们的过滤器以确保我们不会遇到进位冲突：
(-1 AND mask) * shift与预期的全一结果进行比较， -1 << (64-n)（对于 64 位无符号）
当且仅当两者相等时，提取我们的位的魔术移位/乘法才有效。
除了这个非常有趣的问题已经得到很好的答案之外，知道这种按位乘法技巧自 2007 年以来就在计算机国际象棋社区中广为人知，它以Magic BitBoards的名义出现，这可能会很有用。
许多计算机国际象棋引擎使用几个 64 位整数（称为位板）来表示各种棋子集（每个占用的方格 1 位）。假设在某个原点格子上的一个滑动棋子（车、主教、皇后）在K没有阻塞棋子存在的情况下最多可以移动到格子。将那些分散的K位与占用方块的位板一起使用按位与会给出K嵌入在 64 位整数中的特定位字。
魔术乘法可用于将这些分散K的位映射到K64 位整数的低位。然后可以使用这些较低的K位来索引预先计算的位板表，该表表示其原始方块上的块实际上可以移动到的允许方块（注意块块等）
使用这种方法的典型国际象棋引擎有 64 个条目（每个原始方格一个）的 2 个表（一个用于白车，一个用于主教，皇后使用两者的组合），其中包含此类预先计算的结果。评价最高的封闭源代码 ( Houdini ) 和开源国际象棋引擎 ( Stockfish ) 目前都使用这种方法，因为它具有非常高的性能。
Finding these magic multipliers is done either using an exhaustive search (optimized with early cutoffs) or with trial and erorr (e.g. trying lots of random 64-bit integers). There have been no bit patterns used during move generation for which no magic constant could be found. However, bitwise carry effects are typically necessary when the to-be-mapped bits have (almost) adjacent indices.
AFAIK, the very general SAT-solver approachy by @Syzygy has not been used in computer chess, and neither does there appear to be any formal theory regarding existence and uniqueness of such magic constants.