我在一个答案中看到了一种有趣的技术，用于回答另一个问题，我想更好地理解它。
给定一个无符号的64位整数，我们对以下位感兴趣：
1.......2.......3.......4.......5.......6.......7.......8.......
具体而言，我们希望将它们移动到前八个位置，如下所示：
12345678........................................................
我们不关心由 . 指示的位的值，它们也不必保留。
解决方案 是将不需要的位掩码，然后将结果乘以 0x2040810204081。这样做就行了。
这个方法有多通用？这种技术可以用来提取任何子位集吗？如果不能，如何确定该方法是否适用于特定的位集？
最后，如何找到（一种）正确的乘数以提取给定的位？
非常有趣的问题，以及聪明的技巧。
让我们看一个简单的例子，如何操作一个字节。为了简单起见，使用无符号8位数。想象一下你的数字是xxaxxbxx，你想要ab000000。
解决方案由两步组成：位掩码，然后是乘法。位掩码是一个简单的与运算，将不感兴趣的位变成零。在上面的例子中，你的掩码将是00100100，结果将是00a00b00。
现在困难的部分：将其转换为ab......。
乘法是一堆移位和加法操作。关键是允许溢出将我们不需要的位“移走”，并将我们想要的那些位放在正确的位置。
倍增4(00000100)将把所有位向左移动2个单位，并使你达到a00b0000。为了将b向上移动，我们需要乘以1（保持a在正确的位置）+ 4（将b向上移动）。这个总和是5，加上之前的4，我们得到一个神奇的数字20，或00010100。原始掩码后的值是00a00b00；乘法产生：
000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......
通过这种方法，您可以扩展到更大的数字和更多的比特位。
你问的一个问题是“是否可以对任意位数的数字进行这样的操作？” 我认为答案是“不行”，除非您允许进行多个掩码操作或多个乘法操作。问题在于“碰撞”的问题-例如上面问题中的“stray 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 个零，并且在其右侧有 n-m 个零。特别是当位数在重新排序后与原始数字中的顺序不同时，这是对原始标准的重要改进。这意味着，例如，一个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位置，则其左侧需要有m-1个零，右侧需要有n-m个零。”
@Ternary指出，这个规则并不能完全适用，因为在目标区域右侧仅添加一位时就可能发生进位——即当我们要查找的位都是1时。继续上面给出的示例，在一个16位词中紧密包装了五个位：如果我们从以下数字开始：
a...e.b...d..c..
为了简便，我将命名比特位为ABCDEFGHIJKLMNOP
我们将要进行的数学计算是
ABCDEFGHIJKLMNOP
a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00
到目前为止，我们认为在位置 ABCDE 下面任何小于 abcde 的内容都不重要，但事实上，正如 @Ternary 指出的那样，如果 b=1，c=1，d=1，则位置 G 上的 (b+c) 将导致一位进位到位置 F，这意味着位置 F 上的 (d+1) 将进位到 E - 这会破坏我们的结果。请注意，有关感兴趣的最低有效位（在此示例中为 c）右侧的空间并不重要，因为乘法将从最低有效位之外的位置用零填充。
因此，我们需要修改我们的 (m-1)/(n-m) 规则。如果有多个位具有 "恰好 (n-m) 未使用的位"（不包括模式中的最后一位 - 在上面的示例中是 "c"），则我们需要加强规则 - 并且我们必须迭代执行此操作！
我们不仅要查看符合 (n-m) 准则的位数，还要查看位于 (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位设置为1）。3必须向左移动14位，因此我们乘以0x0000000000000400（第14位设置为1）。8 必须向左移动49位，因此我们乘以0x0002000000000000（第49位设置为1）。乘数是各个位的乘数之和。
这只适用于要收集的位不太接近彼此，以便在我们的方案中不属于一起的位的乘法要么超过64位，要么在较低的不关心部分中。
请注意，原始数字中的其他位必须为0。可以通过AND操作对它们进行掩码处理来实现。
（我以前从未见过它。这个技巧太棒了！）
我将进一步解释Floris的断言，即在提取n位时，需要在任何非连续位之间留出n-1个空格：
我的最初想法（一会儿我们会看到这并不完全正确）是您可以做得更好：如果您想要提取n位，则在提取/移位第i位时，如果在i-1位之前或n-i位之后存在任何人（与i位不连续），则会发生冲突。
我将举几个例子来说明：
...a..b...c...有效（a之后的2位没有人，b之前和之后的1位没有人，并且c之前的2位没有人）：
a00b000c
+ 0b000c00
+ 00c00000
= abc.....
...a.b....c...因为b在a之后的2个位上（当我们移动a时，b被拉到了别人的位置），所以失败了：
...a.b....c... Fails because b is in the 2 bits after a (and gets pulled into someone else's spot when we shift a):
a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....
...a...b.c... 因为b在c前面的2位中，所以失败了（当我们移动c时，b被推到其他人的位置）：
a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....
...a...bc...d... 的原因是连续的比特位一起移动：
a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000
但是我们有一个问题。 如果我们使用n-i而不是n-1，我们可能会遇到以下情况：如果我们在我们关心的那部分之外发生冲突，也就是我们最后要掩码掉的部分，但是它的进位位又恰好干扰了重要的非掩码范围呢？（注意：n-1的要求通过确保我们移位第i位时，我们未掩码范围后的i-1位是清除的，以确保这种情况不会发生）
...a...b..c...d... 在进位位上可能出现故障，c在b之后的n-1处，但满足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 的结果 -1 << (64-n)（对于 64 位无符号数）进行比较。
如果两者相等，则通过神奇的移位/乘法提取我们的位的方法才有效。
b最终处于n的位置m，则它需要在其左侧有m-1个零，在其右侧有n-m-1个零。特别是当位不按原始数字中的顺序排列时，这是对原始标准的重要改进。这很有趣。 - FlorisK个方格，如果没有阻挡棋子。使用这些分散的K位与占用方块的位板进行按位与运算，得到一个嵌入在64位整数中的特定K位字。K位映射到64位整数的低K位。然后可以使用这些低K位来索引预先计算的位板表，该表表示棋子在其源方格上实际可以移动到的允许方格（考虑到阻挡棋子等）。