用一次乘法提取位
我看到一个有趣的技术用于解答另一个问题，并希望更好地理解它。
我们给出了一个无符号的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 ，操作是安全的; 如果这不起作用，则再增加一个标准，等等。
我认为，遵循以上的规定会让你的答案很长。
乘法器中的每个1位用于将其中一个位复制到其正确的位置：
1已经处于正确的位置，所以乘以0x0000000000000001 。 2必须向左移位7位，所以我们乘以0x0000000000000080 （设置位7）。 3必须向左移位14位，所以我们乘以0x0000000000000400 （设置位14）。 8必须向左移位49位，所以我们乘以0x0002000000000000 （设置位49）。 乘数是各个位的乘数之和。
这仅仅是因为要收集的比特不太靠近，所以在我们的方案中不属于一起的比特的乘法或者超出了64比特或者更低的不关心部分。
请注意，原始数字中的其他位必须为0 。 这可以通过用AND操作掩盖它们来实现。