使用单个乘法提取位-Java 学习之路

292

我在answer到another question中看到了一种有趣的技术，并希望能够更好地理解它 .

我们给出了一个无符号的64位整数，我们对以下几位感兴趣：

1.......2.......3.......4.......5.......6.......7.......8.......

具体来说，我们希望将它们移到前八位，如下所示：

12345678........................................................

我们不关心 . 指示的位的值，并且不必保留它们 .

solution用于屏蔽不需要的位，并将结果乘以 0x2040810204081 . 事实证明，这就是诀窍 .

这种方法有多普遍？这种技术可以用来提取任何比特子集吗？如果不是，如何判断该方法是否适用于特定的位组？

最后，如何找到（a？）正确的乘数来提取给定的位？

5 回答

230
非常有趣的问题，聪明的伎俩 .

让我们看一个操作单个字节的简单示例 . 使用无符号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......
```
通过这种方法，您可以扩展到更大的数字和更多的位 .

你问的一个问题是"can this be done with any number of bits?"我认为答案是"no"，除非你允许几次掩蔽操作或几次乘法 . 问题是"collisions"的问题 - 例如，上面问题中的"stray b" . 想象一下，我们需要对 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个零，并且在其右侧具有n-m个零 . 特别是当比特在原始数字中的顺序与重新排序后的顺序不同时，这是对原始标准的重要改进 . 这意味着，例如，一个16位字
```
a...e.b...d..c..
```
可以转入
```
abcde...........
```
即使e和b之间只有一个空格，d和c之间只有两个，其他三个之间 . 无论N-1发生了什么？在这种情况下， a...e 变为"one block" - 它们乘以1以最终在正确的位置，因此"we got e for free" . 对于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) 规则："It will always work if there are at least (N-1) spaces between bits; or, if the order of bits in the final result is known, then if a bit b ends up in position m of n, it needs to have m-1 zeros to its left, and n-m zeros to its right."

@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 然后 (b+c) 位置 G 将导致位置 F ，这意味着 (d+1) 位于 F 将携带一点 E - 我们的结果被破坏了 . 请注意，感兴趣的最低有效位（在此示例中为 c ）右侧的空格无关紧要，因为乘法将导致使用零填充从最低有效位开始 .

所以我们需要修改我们的（m-1）/（n-m）规则 . 如果有多个位具有“正好（nm）未使用的位向右（不计算模式中的最后一位 - 上例中的”c“），那么我们需要加强规则 - 我们必须迭代地这样做！

我们不仅要看满足（nm）标准的位数，还要看（nm 1）等的位数 . 让我们将它们的数字称为Q0（正好是 n-m 到下一位），Q1（nm 1）），高达Q（N-1）（n-1） . 那么我们冒险携带if
```
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 ，操作是安全的;如果这不起作用，再增加一个标准，等等 .

我认为按照上述内容将为您提供很长的答案...
回复于 2024-05-03T18:24:03+08:00
150
确实非常有趣的问题 . 我正在用我的两分钱，这就是说，如果你可以通过比特向量理论的一阶逻辑设法说明这样的问题，那么定理证明是你的朋友，并且可以为你提供非常快的速度回答你的问题 . 让我们重新陈述被问到的定理问题：

“存在一些64位常量'掩码'和'被乘数'，这样，对于所有64位位向量x，在表达式y =（x＆mask）*被乘数中，我们得到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 应该可以帮助您入门 .
回复于 2024-05-03T18:24:03+08:00
84
乘法器中的每1位用于将其中一个位复制到正确的位置：
- 1 已经处于正确位置，因此乘以 0x0000000000000001 .
- 2 必须向左移动7位，所以我们乘以 0x0000000000000080 （第7位置位） .
- 3 必须向左移位14位，所以我们乘以 0x0000000000000400 （位14置位） .
- 等等，直到
- 8 必须向左移动49位，所以我们乘以 0x0002000000000000 （设置位49） .
乘数是各个位的乘数之和 .

这只能起作用，因为要收集的位不是太靠近，因此在我们的方案中不属于一起的位的乘法要么超出64位，要么落在较低的无关注部分 .

请注意，原始编号中的其他位必须为 0 . 这可以通过使用AND操作屏蔽它们来实现 .
回复于 2024-05-03T18:24:03+08:00
12
（我以前从未见过它 . 这个技巧很棒！）

我'll expand a bit on Floris'断言当提取 n 位时，你需要在任何非连续位之间留出 n-1 空格：

我最初的想法（我们很好地工作）是你可以做得更好：如果你想提取 n 位，你将有一个如果在之前的 i-1 位或之后的 n-i 位中有任何人（非连续位 i ），则提取/移位位 i 时发生冲突 .

我将举几个例子来说明：

...a..b...c... 工作（ a 之后的2位中没有人， b 之后的位和 c 之前的2位中没有人）：
```
a00b000c
+ 0b000c00
+ 00c00000
= abc.....
```
...a.b....c... 失败，因为 b 在 a 之后的2位中（当我们移动 a 时被拉入别人的位置）：
```
a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....
```
...a...b.c... 失败，因为 b 在 c 之前的2位中（当我们移动 c 时被推入别人的位置）：
```
a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....
```
...a...bc...d... 因连续位移位而起作用：
```
a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000
```
But we have a problem. 如果我们使用 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 位空间”的要求呢？ Because we can do better ：

...a....b..c...d.. 失败了“ n-1 位空间”测试，但适用于我们的位提取技巧：
```
+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......
```
我无法想出一个很好的方法来表征这些在重要位之间没有 n-1 空间的字段，但仍然可以用于我们的操作 . 但是，自 we know ahead of time 以来我们经历了进位冲突：

将 (-1 AND mask) * shift 与预期的全1结果进行比较， -1 << (64-n) （对于64位无符号）

当且仅当两者相等时，魔术移位/乘法才能提取我们的位 .
回复于 2024-05-03T18:24:03+08:00
29

除了对这个非常有趣的问题的已经很好的答案之外，知道这个按位乘法技巧自2007年以来在计算机国际象棋界已经知道，其名称为Magic BitBoards可能是有用的 .

许多计算机国际象棋引擎使用几个64位整数（称为位板）来表示各种组件集（每个占用方块1位） . 假设如果没有阻挡件，某个原点上的滑块（车，主教，女王）可以移动到最多 K 个方块 . 使用bitwise和那些分散的 K 位与占用方块的位板给出了一个嵌入在64位整数内的特定 K 位字 .

可以使用Magic multiplication将这些分散的 K 位映射到64位整数的低 K 位 . 然后可以使用这些较低的 K 位来索引预先计算的位板表，该位表示其原点上的块可以实际移动到的允许方块（处理阻塞件等）

使用这种方法的典型国际象棋引擎有两个表（一个用于车，一个用于主教，两个使用两者的组合），64个条目（每个原始方格一个）包含这样的预先计算结果 . 最高评级的闭源（Houdini）和开源象棋引擎（Stockfish）目前都使用这种方法，因为它具有非常高的性能 .

使用exhaustive search（使用早期截止优化）或使用trial and erorr（例如尝试大量随机64位整数）来查找这些魔术乘数 . 在移动生成期间没有使用位模式，其中没有找到魔法常数 . 然而，当待映射比特具有（几乎）相邻索引时，通常需要逐位进位效应 .

AFAIK是@Syzygy非常普遍的SAT求解器，它没有被用于计算机象棋，也没有关于这种魔法常数的存在性和唯一性的任何形式理论 .

回复于 2024-05-03T18:24:03+08:00

使用单个乘法提取位

5 回答

相关问题