使用单个乘法提取位

Question

我看到在使用了一个有趣的技术,答案到另一个问题,并想好一点理解.

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

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

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

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

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

该溶液是屏蔽掉不需要的位,并且乘以结果0x2040810204081.事实证明,这就是诀窍.

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

最后,如何找到(a？)正确的乘数来提取给定的位？

Answer 1

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

让我们看一个操作单个字节的简单示例.使用无符号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.按照早期的方法,你会认为我们需要{x 2,x {1 + 4 + 16}} = x 42(噢 - 一切的答案!).结果:

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

正如你所看到的,它仍然有效,但"只是".它们的关键在于我们想要的位之间有足够的空间,我们可以挤压一切.我无法在c之后添加第四位,因为我会得到实例,我得到c + d,位可能携带,...

因此,如果没有正式的证据,我会回答你问题中更有趣的部分如下:"不,这对任意数量的位都不起作用.要提取N位,你需要(N-1)个空格你想要的位数提取,或者有额外的掩码倍增步骤."

我能想到的唯一例外是"必须在位之间有(N-1)个零"规则是这样的:如果你想提取原始中彼此相邻的两个位,并且你希望将它们保留在同样的顺序,那么你仍然可以做到这一点.并且出于(N-1)规则的目的,它们被计为两位.

还有另一种见解 - 受以下@Ternary答案的启发(见我在那里的评论).对于每个有趣的位,您只需要在其右侧有多个零,因为您需要空间用于需要去那里的位.但是,它左边需要尽可能多的位,因为左边有结果位.因此,如果位b在n的位置m结束,则它需要在其左侧具有m-1个零,并且在其右侧具有nm零.特别是当比特在原始数字中的顺序与重新排序后的顺序不同时,这是对原始标准的重要改进.这意味着,例如,一个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最终位于位置m,则n,它的左边需要m-1个零,右边需要nm."

@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)/(nm)规则.如果有多个位具有"正好(nm)未使用的位向右(不计算模式中的最后一位 - 上例中的"c"),那么我们需要加强规则 - 我们必须迭代地这样做!

我们不仅需要查看符合(nm)标准的位数,还要查看(n-m + 1)处的位数.让我们将它们的数字称为Q0(确切地说n-m是下一位),Q1( n-m + 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; 如果这不起作用,再增加一个标准,等等.

我认为按照上述内容将为您提供很长的答案...

Answer 2

确实非常有趣的问题.我正在用我的两分钱,这就是说,如果你可以通过比特向量理论的一阶逻辑设法说明这样的问题,那么定理证明是你的朋友,并且可以为你提供非常快的速度回答你的问题.让我们重新陈述被问到的定理问题:

"存在一些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应该让你开始.

Answer 3

乘法器中的每1位用于将其中一个位复制到正确的位置:

• 1已经处于正确的位置,所以乘以0x0000000000000001.
• 2必须向左移动7位位置,所以我们乘以0x0000000000000080(第7位置位).
• 3必须向左移位14位,所以我们乘以0x0000000000000400(第14位置位).
• 等等,直到
• 8必须向左移动49位,所以我们乘以0x0002000000000000(第49位设置).

乘数是各个位的乘数之和.

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

请注意,原始编号中的其他位必须是0.这可以通过使用AND操作屏蔽它们来实现.

Answer 4

(我以前从未见过它.这个技巧很棒!)

我将对Floris的断言进行一些扩展,即在提取n位时,您需要n-1在任何非连续位之间留出空格:

我最初的想法(我们会在一分钟内看到这不起作用)是你可以做得更好:如果你想提取n比特,i如果你有任何人,你在提取/移位时会发生碰撞(非- i在i-1前面的位或n-i后续的位中连接).

我将举几个例子来说明:

...a..b...c...可以工作(a之前的2位,之前的位b和后面的位,没有人在之前的2位c):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...a.b....c...失败,因为b它在2位之后a(当我们转移时被拉到别人的位置a):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...b.c...失败,因为b前面的2位c(当我们移位时被推入别人的位置c):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... 因为连续位一起移动而起作用:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

但是我们遇到了问题.如果我们使用n-i而不是n-1我们可能有以下情况:如果我们在我们关心的部分之外发生碰撞,那么我们会在结束时屏蔽掉,但是其进位最终会干扰重要的未屏蔽范围？(并注意:该n-1要求确保通过确保i-1在我们移位i第二位时我们的未屏蔽范围之后的位清零)不会发生这种情况

...a...b..c...d...进位的潜在失败c在于n-1之后b,但满足n-i标准:

  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与预期的all-one结果进行比较,-1 << (64-n)(对于64位无符号)

当且仅当两者相等时,魔术移位/乘法才能提取我们的位.

Answer 5

除了对这个非常有趣的问题已经很好的答案之外,知道这个按位乘法技巧自2007年以来一直在计算机国际象棋界已知,其中它以Magic BitBoards的名义.

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

魔术乘法可用于将这些散乱K位映射到K64位整数的低位.K然后可以使用这些较低位来索引预先计算的位板表,该位表示其原点上的块可以实际移动到的允许方块(处理阻塞件等)

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

使用穷举搜索(使用早期截止优化)或使用试验和错误(例如,尝试大量随机64位整数)来查找这些魔术乘数.在移动生成期间没有使用位模式,其中没有找到魔法常数.然而,当待映射比特具有(几乎)相邻索引时,通常需要逐位进位效应.

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