用一个乘法提取位
我看到一个有趣的技术用于解答 另一个问题 ，并希望更好地理解它。
我们得到一个无符号的64位整数，我们对以下几点感兴趣：
1.......2.......3.......4.......5.......6.......7.......8....... 具体来说，我们想把他们移到前八名，如下所示：
12345678........................................................
我们不关心所表示的位的值. ，而且不必保存。
解决方法是屏蔽不需要的位，并将结果乘以0x2040810204081 。 事实certificate，这是一个窍门。
这种方法有多普遍？ 这种技术可以用来提取任何位的子集？ 如果不是，那么如何判断这个方法是否适用于一组特定的位？
最后，如何find（a？）正确的乘法器来提取给定的位？
非常有趣的问题，聪明的把戏。
我们来看看获取单个字节的一个简单例子。 使用无符号8位简单。 想象一下你的号码是xxaxxbxx ，你想要ab000000 。
解决scheme由两个步骤组成：位掩码，然后是乘法。 位掩码是一个简单的AND操作，将不感兴趣的位变为零。 在上面的例子中，你的掩码是00100100 ，结果是00a00b00 。
现在困难的部分：把它变成ab......
乘法是一堆移位和加法运算。 关键是让溢出“移走”我们不需要的位，并把我们想要的位置放在正确的位置。
乘以4（ 00000100 ）会把所有的东西都a00b0000 2，然后把你变成a00b0000 。 为了让b向上移动，我们需要乘以1（保持a在正确的位置）+4（将b向上移动）。 这个数字是5，加上前面的4，我们得到一个20或者00010100的魔法数字。 掩蔽后原来是00a00b00 ; 乘法给出：
000000a00b000000 00000000a00b0000 + ---------------- 000000a0ab0b0000 xxxxxxxxab......
从这种方法你可以扩大到更大的数字和更多的位。
你问的问题之一是“这可以用任何位数来完成吗？” 我认为答案是“否”，除非你允许几个屏蔽操作或几个乘法。 问题在于“碰撞”问题 – 例如上面问题中的“stream浪b”。 想象一下，我们需要像xaxxbxxcx这样的xaxxbxxcx 。 按照前面的方法，你会认为我们需要{x 2，x {1 + 4 + 16}} = x 42（oooh – 对所有事物的回答！ 结果：
00000000a00b00c00 000000a00b00c0000 0000a00b00c000000 ----------------- 0000a0ababcbc0c00 xxxxxxxxabc......
正如你所看到的，它仍然有效，但“只是”。 他们在这里的关键是，我们想要的东西之间有足够的空间，我们可以挤压一切。 我不能在c之后添加第四位d，因为我会得到c + d的实例，位可能带有…
因此，如果没有正式的certificate，我会回答你的问题更有趣的部分如下：“不，这不适用于任何位数。要提取N位，你需要（N-1）之间的空格提取，或者有额外的蒙版乘法步骤“。
唯一的例外，我可以想到的“必须有（N-1）位之间的零”规则是这样的：如果你想提取两个在原来相邻的位，并且你想保持它们在同样的顺序，那么你仍然可以做到这一点。 就（N-1）规则而言，它们算作两位。
还有另外一个见解 – 受到下面的@Ternary的回答的启发（请参阅我的评论）。 对于每一个有趣的位，你只需要在它的右边那么多的零，因为你需要空间来存放需要去的位。 而且，它需要尽可能多的位左侧，因为它有结果位左侧。 所以如果一个位b在n的位置m结束，那么它需要在其左边有m-1个零点，在其右边有零个零点。 特别是当原始数字中的位数与重新sorting后的位数不同时，这是对原始标准的重要改进。 这意味着，例如，一个16位字
a...eb..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)规则：“如果位之间至less有（N-1）个空格，它将一直工作，或者如果最终结果中的位的顺序已知，那么如果一个位b结束在n的位置m上，它的左边需要m-1个零点，右边需要零个nm零点。
@Ternary指出，这个规则并不是很有效，因为可以从“在目标区域的右侧”增加一些位，即当我们要查找的位全是1时。 继续我用上面给出的五个紧密排列的16位字的例子：如果我们开始
a...eb..d..c..
为了简单起见，我将命名位置ABCDEFGHIJKLMNOP
我们要做的math是
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）/（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 ...
如果你看这个，你可以看到，如果你写一个简单的mathexpression式
W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)
结果是W > 2 * N ，那么你需要将RHS标准增加一位到(n-m+1) 。 此时，只要W < 4 ，手术是安全的。 如果不行的话，再增加一个标准。
我认为，继上述会让你很长的路要回答你的答案…
确实非常有趣的问题。 我正在用我的两个分钱来争取，那就是，如果你能用位向量理论的一阶逻辑来设法解决这样的问题，那么定理certificate者就是你的朋友，并且可以为你提供非常快的回答你的问题。 让我们重新陈述被问到的问题是一个定理：
“存在一些64位常量”掩码“和”被乘数“，对于所有64位位向量x，在expression式y =（x＆mask）*中，我们有y.63 == x.63 ，y.62 == x.55，y.61 == x.47等“
如果这个句子实际上是一个定理，那么常量“掩码”和“被乘数”的某些值就是满足这个性质的。 所以让我们用一个定理certificate者可以理解的东西来表示：SMT-LIB 2input：
(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)
现在我们来问定理certificate者Z3这是否是一个定理：
z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2
结果是：
sat (model (define-fun mask () (_ BitVec 64) #x8080808080808080) (define-fun multiplicand () (_ BitVec 64) #x0002040810204081) )
答对了！ 它在0.06秒内再现原始文章中给出的结果。
从更一般的angular度来看，我们可以把它看作是一阶程序综合问题的一个实例，这是一个新兴的研究领域，关于哪些论文已经发表。 search"program synthesis" filetype:pdf应该让你开始。
乘法器中的每个1位用于将其中一个位复制到其正确的位置：
-
1已经在正确的位置，所以乘以0x0000000000000001。 -
2必须向左移位7位，所以我们乘以0x0000000000000080（位7被设置）。 -
3必须向左移位14位，所以我们乘以0x0000000000000400（位14被设置）。 - 等等
-
8必须向左移位49位，所以我们乘以0x0002000000000000（位49被设置）。
乘数是各个位的乘数之和。
这仅仅是因为要收集的比特不是太靠近在一起，所以在我们的scheme中不属于一起的比特的乘法或者超出了64比特或者更低的不关心部分。
请注意，原始数字中的其他位必须为0 。 这可以通过用AND操作掩盖它们来实现。
（我以前从来没有见过这个技巧太棒了！）
在Floris的断言中，我将扩展一点，当提取n位时，在任何非连续位之间需要n-1空格：
我最初的想法（我们会在一分钟内看到这是不是很有效），你可以做得更好：如果你想提取n位，如果你有任何人， （与比特i不连续）在之前的i-1比特或之后的ni比特中。
我将举几个例子来说明：
...a..b...c...工作（在a之后的2位中没有人， b之前的位和b之后的位，没有人在c之前的2位中）：
a00b000c + 0b000c00 + 00c00000 = abc.....
...ab...c...失败，因为b在b之后的2个位（并且当我们转移a时被拉进别人的位置）：
a0b0000c + 0b0000c0 + 00c00000 = abX.....
...a...bc..失败，因为b位于c之前的2位（当我们移位c时，被推入别人的位置）：
a000b0c0 + 0b0c0000 + b0c00000 = Xbc.....
...a...bc...d...因为连续的位移一起工作：
a000bc000d + 0bc000d000 + 000d000000 = abcd000000
但是我们有一个问题。 如果我们使用ni而不是n-1我们可以有以下情况：如果我们关心的部分之外有一个碰撞，那么我们将在最后掩盖掉一些东西，但是哪个进位比特最终会干扰重要的不被掩盖的范围？ （并且注意： n-1要求确保在我们移动第i位时确保在我们的未被屏蔽的范围之后的i-1位清除时不发生这种情况）
...a...b..c...d...进位位上的潜在故障， c在b之后n-1 ，但满足ni标准：
a000b00c000d + 0b00c000d000 + 00c000d00000 + 000d00000000 = abcdX.......
那么为什么我们不回到“ n-1位空间”的要求呢？ 因为我们可以做得更好 ：
...a....b..c...d.. 失败的“ n-1位空间”testing，但为我们的位提取技巧：
+ a0000b00c000d00 + 0b00c000d000000 + 00c000d00000000 + 000d00000000000 = abcd...0X......
我不能想出一个很好的方法来表征这些在重要位之间没有 n-1空间的领域，但是仍然会为我们的运作起作用。 但是，由于我们提前知道哪些位是我们感兴趣的，所以我们可以检查我们的filter以确保我们不会遇到进位冲突：
比较(-1 AND mask) * shift和预期的全1结果， -1 << (64-n) （对于64位无符号）
当且仅当两者相等时，神奇的移位/乘法才能提取我们的位。
除了对这个非常有趣的问题已经很好的答案之外，知道这个逐位乘法技巧在2007年以来就已经在计算机象棋社区中被知道了，在那里它被称为Magic BitBoards 。
许多计算机国际象棋引擎使用几个64位整数（称为位板）来表示不同的棋子组（每个占用方块1位）。 假设某个原点广场上的滑动件（白嘴鸦，主教，女王）可以移动到最多K方格，如果没有阻塞件存在的话。 在占位方块的位板上使用逐位和分散的K位给出embedded在64位整数内的特定K位字。
魔术乘法可用于将这些分散的K位映射到64位整数的较低K位。 然后可以使用这些较低的K位来索引一张预先计算的位板表，该位表示原始方块上实际可移动的允许的方块（考虑到阻塞块等）
一个典型的使用这种方法的国际象棋引擎有64个条目（每个原点平方一个）包含这些预先计算结果的2个表（一个用于白嘴鸦，一个用于主教，两个用于两者的皇后）。 目前最高等级的闭源（ Houdini ）和开源国际象棋引擎（ Stockfish ）都使用这种方法，因为它的性能非常高。
寻找这些神奇的乘法器或者使用穷举search （使用早期截断进行优化），或者使用trial和erorr （例如尝试大量随机的64位整数）。 移动生成过程中没有使用位模式，因此没有发现魔法常量。 然而，当要映射的位具有（几乎）相邻的索引时，通常需要逐位进位效应。
AFAIK，@Syzygy最常用的SAT解决方法尚未用于计算机象棋，似乎也没有任何有关这类魔术常数的存在和唯一性的forms理论。
