我看到在使用了一个有趣的技术， 答案到另一个问题 ，并想好一点理解。
我们给出的64位无符号整数，我们感兴趣的是以下位：
1.......2.......3.......4.......5.......6.......7.......8.......
具体来说，我们希望将其移动到前八的位置，就像这样：
12345678........................................................
我们不关心所指示的比特值. 和他们没有被保存。
该溶液是屏蔽掉不需要的位，并且通过乘以结果0x2040810204081 。 这一点，因为它的出现，是卓有成效的。
如何一般是这种方法吗？ 可这种技术被用来提取位的任何子集？ 如果没有，如何做一个弄不清方法是否适用于特定的一组位？
最后，一个人如何会去寻找（一个？）正确的乘数提取给定的位？
非常有趣的问题，和聪明的把戏。
让我们来看看越来越操纵单个字节的一个简单的例子。 使用无符号的8位为简单起见。 试想一下，你的电话号码是xxaxxbxx ，你想ab000000 。
该解决方案包括两个步骤：a位掩码，随后乘法。 该位掩码是一个简单的操作，变成无趣位为零。 在上述情况下，你的面具是00100100 ，结果00a00b00 。
现在最困难的部分：即转成ab...... 。
乘法是一堆换档和附加操作。 关键是要允许溢出“上移开”我们不需要位，并把我们想要的那些在正确的地方。
乘以4（ 00000100 ）将转移一切由2左，让你a00b0000 。 为了让b向上移动，我们需要通过1相乘（以保持在一个合适的位置）+ 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......
正如你所看到的，它仍然有效，但“才刚刚”。 他们这里的关键是，有“足够的空间”，我们要位之间，我们可以挤一切。 ℃之后我不能添加第四位d正确的，因为我会得到从哪里获得C + d的情况下，位可能携带，...
因此，没有正式的证据，我会回答你的问题的更有趣的部分如下：“不，这不会对任何位数的工作，要提取N位，你需要要位之间（N-1）空间提取物，或具有附加的掩模 - 乘法的步骤“。
我可以想到的唯一例外“必须有（N-1）位之间零”的规则是这样的：如果你想提取两位是相邻的原对方，你想保留他们在相同的顺序，那么你仍然可以做到这一点。 而对于（N-1）的规则的目的，它们算作两个比特。
还有另一种见解 - 通过@Ternary的下面的答案启发（见我的评论那里）。 对于每一个有趣的一点，你只需要空间，需要去那里位需要尽可能多的零到它的右侧。 但同时，它需要许多位向左，因为它已经带来了位到左侧。 因此，如果位b在n个的位置m结束的话，就需要有m-1个零到其左，纳米零其右侧。 尤其是当位不是在原来的号码，因为他们将重新排序后的顺序相同，这是原来的标准，一个重要的改进。 这意味着，例如，一个16位字
a...e.b...d..c..
可以移入
abcde...........
即使有两个d和C之间，其他人之间的三个E和B之间只有一个空间。 无论发生在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端向上在正的位置m，它需要有M-1个零其左，和纳米零其右侧“。
@Ternary指出，这条规则也并非完全奏效，因为可以从加入“只是目标区域右侧的”位进位 - 即，当我们正在寻找的位全部为一。 我继续在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则(b+c)的位置G会造成位进行定位F ，这意味着(d+1)在适当的位置F将携带位插入E -和我们的结果是损坏的。 需要注意的是空间，感兴趣的至少显著位的右边（ c在这个例子中）不要紧，因为乘法会导致填充与beyone最低显著位零。
因此，我们需要修改我们的（M-1）/（nm）的规则。 如果是具有“精确（nm）的未使用的位到右侧（不包括在模式的最后一位 - ‘在上面的例子C’）不止一位，那么我们需要加强规则 - 我们必须这样做反复！
我们不仅要在满足（nm）的标准位的数量看，还以为是在（NM + 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位常量‘掩模’和‘被乘数’，使得对于所有的64位bitvectors X，在表达式y =（x＆掩模）*被乘数，我们有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 。 这可以通过使用与操作，掩盖他们来实现。
（我从来没有见过它。这招真是太棒了！）
我会扩大弗洛里斯的说法，有点那个解压时n位需要n-1的任何非连续的位之间的空间：
我最初的想法（我们将在一分钟内如何完全不是那么回事看）是，你可以做的更好：如果你想提取n位，解压时你就会有一个碰撞/换挡位i如果有任何人（非连续的与位i ）中i-1比特前面或ni位之后。
我举几个例子来说明：
...a..b...c...工作（没有人在2位后a ，前位和后的比特b ，没有人在之前的2位c ）：
a00b000c
+ 0b000c00
+ 00c00000
= abc.....
...ab...c...失败，因为b是在2位后a （当我们转向被拉到别人的斑a ）：
a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....
...a...bc..失败，因为b是在之前的2位c （当我们转向被压入别人的现货c ）：
a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....
...a...bc...d...工作，因为连续的比特一起偏移：
a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000
但是我们有一个问题。 如果我们使用ni代替n-1我们可以有以下情形：如果我们有我们关心的部分以外的碰撞，这是我们将在年底掩盖掉，但其进位结束的重要干扰未屏蔽的范围是多少？ （和注意： n-1要求确保这不会通过确保发生i-1我们未屏蔽的范围后位是明确的，当我们转移了i个位）
...a...b..c...d...上搬入位潜在的故障， c是在n-1后b ，但满足ni标准：
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年以来，哪里就有奇迹的名义下被称为魔术位棋盘 。
许多计算机下棋引擎使用几个64位的整数（称为位棋盘）表示各种片组（每平方占用1个比特）。 假设在某一原点方形的滑动件（车，象，后）最多可以移动到K正方形如果没有挡片存在。 使用按位和的那些分散K与占用的正方形的棋盘位给出了一个具体的K嵌入一个64位整数中的比特字。
魔法乘法可以用于这些分散的映射K位到下K一个64位整数的比特。 这些较低K然后比特可被用于索引该representst允许的正方形预先计算的位棋盘的一个表，其来源正方形的片实际上可以移动到（考虑挡片等的保健）
使用这种方法的典型的国际象棋发动机具有2个表（一个用于乌鸦，一个用于主教，利用两者的组合蚁）含有这样的预先计算的结果64个条目（每平方原点的一个）的。 无论是收视率最高的闭源（ 胡迪尼 ）和开源的国际象棋引擎（ 鱼干 ）目前使用这种方法进行了非常高的性能。
发现这些神奇的乘数完成要么使用穷举搜索 （早期截止优化）或试erorr （如争取大量的随机64位整数）。 已经有招代过程中没有使用的位模式对于没有魔法常数可能被发现。 然而，逐位进位影响通常在必要时将要被映射的比特有（几乎）相邻的索引。
据我所知，通过@Syzygy的很一般的SAT求解器approachy尚未在计算机国际象棋中使用，而且也不存在似乎是关于生存和这样的魔术常量的独特任何正式的理论。
