用一次乘法提取位
我看到一个有趣的技术用于解答另一个问题，并希望更好地理解它。
我们给出了一个无符号的64位整数，我们对以下几点感兴趣：
1.......2.......3.......4.......5.......6.......7.......8.......
具体来说，我们希望将它们移动到前八位，如下所示：
12345678........................................................
我们不关心由表示的位的值. ，而且他们不必保存。
解决方案是屏蔽不需要的位，并将结果乘以0x2040810204081 。 事实证明，这是一个窍门。
这种方法有多普遍？ 这种技术可以用来提取任何位的子集吗？ 如果不是，那么如何确定该方法是否适用于特定的一组位？
最后，如何找到（a？）正确的乘法器来提取给定的位？
非常有趣的问题和巧妙的把戏。
我们来看看获取单个字节的一个简单例子。 使用无符号8位来简化。 想象一下你的号码是xxaxxbxx ，你想要ab000000 。
该解决方案由两个步骤组成：位掩码，然后是乘法。 位掩码是一种简单的AND操作，可将不感兴趣的位变为零。 在上面的例子中，你的掩码是00100100 ，结果是00a00b00 。
现在最难的部分是：把它变成ab......
乘法是一堆移位和加法操作。 关键是允许溢出来“移走”我们不需要的位，并将我们想要的位放在正确的位置。
乘以4（ 00000100 ）会将所有东西左移2，并让你成为a00b0000 。 为了让b向上移动，我们需要乘以1（保持a在正确的位置）+4（将b向上移动）。 这个总数是5，并且与前面的4相加，我们得到20或00010100的幻数。 掩蔽后原始00a00b00 ; 乘法给出：
000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......
从这种方法你可以扩展到更大的数字和更多的位。
你问的其中一个问题是“这可以用任何位数来完成吗？” 我认为答案是“否”，除非你允许进行几次掩蔽操作或几次乘法。 问题是“碰撞”问题 - 例如，上述问题中的“流浪b”。 想象一下，我们需要对xaxxbxxcx这样的数字执行此xaxxbxxcx 。 按照先前的方法，你会认为我们需要{x 2，x {1 + 4 + 16}} = x 42（oooh - 对所有事物的答案！）。 结果：
00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......
正如你所看到的，它仍然有效，但“只是”。 他们关键在于我们想要的东西之间有“足够的空间”，我们可以挤压一切。 我不能在c之后添加第四个d，因为我会得到c + d的实例，位可能带有......
因此，如果没有正式的证明，我会回答您的问题中更有趣的部分，如下所示：“不，这不适用于任何位数。要提取N位，您需要（N-1）个位之间的空格提取，或者有额外的蒙版乘法步骤。“
我能想到的唯一的例外是“位之间必须有（N-1）个零”的规则是这样的：如果你想提取两个在原件中彼此相邻的位，并且你想让它们保持在相同的顺序，那么你仍然可以做到这一点。 为了（N-1）规则的目的，它们计为两位。
还有另外一个见解 - 受到以下@Ternary回答的启发（请参阅我的评论）。 对于每个有趣的位，您只需要尽可能多的零，因为您需要空间来存放需要到达的位。 而且，它需要尽可能多的位左边，因为它有结果位左边。 所以如果一个位b在n的位置m结束，那么它需要在其左边有m-1个零点，在它的右边需要有零个零点。 特别是当原始数字中的位数与重新排序后的位数不同时，这是对原始标准的重要改进。 这意味着，例如，一个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个零点，在右边有零个零点。“
@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 ，这意味着(d+1)在适当的位置F将携带位插入E -和我们的结果是损坏的。 请注意，感兴趣的最低有效位（本例中为c ）右侧的空间无关紧要，因为乘法将导致填充零，即从最低有效位开始填充。
所以我们需要修改我们的（m-1）/（nm）规则。 如果多于一个比特的右侧有“精确（nm）未使用的比特数（不包括该模式中的最后一个比特 - 上述示例中的”c“），那么我们需要加强规则 - 我们必须反复做！
我们不仅要看看满足（nm）标准的位数，还要看看在（n-m + 1）处的位数等等。我们称它们的数量Q0（恰好为nm到下一位），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位位向量x，在表达式y =（x＆mask）*被乘数中存在一些64位常量'掩码'和'被乘数'，我们有y.63 == x.63 ，y.62 == x.55，y.61 == x.47等“
如果这句话实际上是一个定理，那么常量'掩码'和'被乘数'的某些值就是满足这个性质的。 所以让我们用定理证明者可以理解的东西来描述这个问题，即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操作掩盖它们来实现。