314

別の質問への回答で興味深いテクニックが使用されているのを見たので、もう少し理解を深めたいと思います。

符号なし 64 ビット整数が与えられ、次のビットに関心があります。

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

具体的には、次のように上位 8 位まで移動させたいと考えています。

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

で示されるビットの値は気.にせず、保持する必要もありません。

解決策は、不要なビットをマスクして、結果に を掛けることでした0x2040810204081。結局のところ、これはうまくいきます。

この方法はどの程度一般的ですか？この手法を使用してビットのサブセットを抽出できますか? そうでない場合、その方法が特定のビットのセットに対して機能するかどうかをどのように判断しますか?

最後に、与えられたビットを抽出するための (a?) 正しい乗数を見つけるにはどうすればよいでしょうか?

4

5 に答える 5

244

非常に興味深い質問であり、巧妙なトリックです。

単一バイトを操作する簡単な例を見てみましょう。簡単にするために符号なし 8 ビットを使用します。xxaxxbxxあなたの番号が であり、あなたが望むと想像してくださいab000000。

このソリューションは、ビット マスキングとその後の乗算の 2 つのステップで構成されていました。ビット マスクは、不要なビットをゼロにする単純な AND 演算です。上記の場合、マスクは00100100結果になり00a00b00ます。

ここで難しいのは、それを に変換することab......です。

乗算は、一連のシフトと加算の演算です。重要なのは、オーバーフローによって不要なビットを「シフト」し、必要なビットを適切な場所に配置できるようにすることです。

4 ( 00000100) を掛けると、すべてが 2 だけ左にシフトし、 になりますa00b0000。をb上に移動するには、1 (a を正しい位置に保つため) + 4 (b を上に移動するため) を掛ける必要があります。この合計は 5 で、前の 4 と組み合わせると 20 のマジック ナンバー、つまり00010100. オリジナルは00a00b00マスキング後。乗算は次のようになります。

000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......

このアプローチから、より大きな数とより多くのビットに拡張できます。

あなたが尋ねた質問の 1 つは、「これは任意の数のビットで実行できますか?」というものでした。いくつかのマスキング操作または複数の乗算を許可しない限り、答えは「いいえ」だと思います。問題は「衝突」の問題です。たとえば、上記の問題の「stray b」です。のような数に対してこれを行う必要があると想像してくださいxaxxbxxcx。前のアプローチに従えば、{x 2, x {1 + 4 + 16}} = x 42 (うわー、すべての答えです!) が必要だと思うでしょう。結果：

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

ご覧のとおり、まだ機能しますが、「ただ」です。ここで重要なのは、必要なビット間に「十分なスペース」があり、すべてを詰め込むことができるということです。c の直後に 4 番目のビット d を追加することはできませんでした。

したがって、正式な証明がなければ、あなたの質問のより興味深い部分に次のように答えます。抽出するか、追加のマスク乗算手順を実行してください。」

「ビット間に (N-1) 個のゼロがなければならない」というルールの唯一の例外は次のとおりです。同じ順序であれば、引き続き実行できます。また、(N-1) ルールの目的上、それらは 2 ビットとしてカウントされます。

以下の@Ternaryの回答に触発された別の洞察があります（私のコメントを参照してください）。興味深いビットごとに、そこに行く必要があるビットのスペースが必要なだけ、その右側にゼロが必要です。しかしまた、左側に結果ビットがあるのと同じ数のビットが左側に必要です。したがって、ビット b が n の m の位置にある場合、左に m-1 個のゼロ、右に nm 個のゼロが必要です。特に、ビットが元の数で並べ替え後の順序と同じでない場合、これは元の基準に対する重要な改善です。これは、たとえば、16 ビット ワードが

a...e.b...d..c..

にシフトすることができます

abcde...........

e と b の間には 1 つのスペースしかなく、d と c の間には 2 つ、他のスペースの間には 3 つしかありません。N-1はどうしたの？？この場合、a...eは「1 つのブロック」になります。それらは 1 で乗算され、適切な場所に配置されるため、「無料で e を取得しました」。同じことが b と d にも当てはまります (b には右側に 3 つのスペースが必要であり、d には同じように左側に 3 つのスペースが必要です)。したがって、マジック ナンバーを計算すると、重複があることがわかります。

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 ビット ワード内の密集した 5 ビットで続けると、次のようになります。

a...e.b...d..c..

簡単にするために、ビット位置に名前を付けますABCDEFGHIJKLMNOP

私たちがやろうとしていた数学は

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00

これまで、abcde(positions ABCDE) の下にあるものは問題ではないと考えていましたが、実際には @Ternary が指摘したようb=1, c=1, d=1に、(b+c)in positionGが少しを position に運ぶ場合F、つまり(d+1)in positionFはビットをE-にキャリーします。結果はだめです。対象の最下位ビット (cこの例では) の右側のスペースは問題にならないことに注意してください。これは、乗算によって最下位ビットを超えてゼロがパディングされるためです。

したがって、(m-1)/(nm) ルールを変更する必要があります。「ちょうど (nm) 個の未使用ビットが右側にある (パターンの最後のビット - 上記の例では "c" を数えない) というビットが複数ある場合、ルールを強化する必要があります - そして、繰り返してください！

(nm) 基準を満たすビット数だけでなく、(n-m+1) にあるビット数なども調べる必要があります。それらの数を Q0 (正確n-mには次のビットまで)、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 基準を 1 ビット増やして にする必要があります(n-m+1)。この時点で、操作は安全W < 4です。それでもうまくいかない場合は、基準をもう 1 つ増やします。

上記に従うことで、あなたの答えに長い道のりが得られると思います...

于 2013-01-27T12:27:51.370 に答える
159

確かに非常に興味深い質問です。私は 2 セントに賛成です。つまり、このような問題をビットベクトル理論に対する 1 次論理の観点から述べることができれば、定理証明者はあなたの友人であり、潜在的に非常に迅速に提供できるということです。あなたの質問への答え。定理として求められている問題をもう一度述べましょう。

「いくつかの 64 ビット定数 'マスク' と '被乗数' が存在するため、すべての 64 ビット ビットベクトル x に対して、式 y = (x & マスク) * 被乗数で、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 秒で再現します。

これをより一般的な観点から見ると、これは 1 次プログラム合成問題のインスタンスであると見なすことができます。これは、ほとんど論文が発表されていない研究の初期領域です。の検索"program synthesis" filetype:pdfから始めてください。

于 2013-01-27T20:19:39.277 に答える
89

乗数の各 1 ビットは、ビットの 1 つを正しい位置にコピーするために使用されます。

  • 1はすでに正しい位置にあるので、 を掛け0x0000000000000001ます。
  • 2左に 7 ビット位置シフトする必要があるため、乗算し0x0000000000000080ます (ビット 7 が設定されます)。
  • 3左に 14 ビット位置シフトする必要があるため、乗算し0x0000000000000400ます (ビット 14 が設定されます)。
  • などなど
  • 8左に 49 ビット位置シフトする必要があるため、乗算し0x0002000000000000ます (ビット 49 が設定されます)。

乗数は、個々のビットの乗数の合計です。

これが機能するのは、収集されるビットが互いに近すぎないためです。そのため、私たちのスキームで一緒に属していないビットの乗算は、64 ビットを超えるか、下位の don't-care 部分に収まります。

元の数値の他のビットは でなければならないことに注意してください0。これは、AND 演算でマスクすることで実現できます。

于 2013-01-27T12:57:15.673 に答える
29

（今まで見たことがない。このトリックは素晴らしい！）

ビットを抽出するとき、連続していないビット間にスペースnが必要であるという Floris の主張を少し拡張します。n-1

私の最初の考え (これがどのように機能しないかはすぐにわかります) は、もっとうまくやれるだろうということでした:nビットを抽出したい場合、ビットを抽出/シフトするときに衝突が発生しiます-先行するビットまたは後続のビットで bit i) と連続。i-1n-i

説明するためにいくつかの例を挙げます。

...a..b...c...動作します ( の 2 ビット後a、 の前のビット と の後のビット に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と、次のようなシナリオが考えられます: 重要な部分の外側で衝突が発生し、最後に何かをマスクして除去したものの、そのキャリー ビットがマスクされていない重要な範囲で干渉してしまった場合? (注:要件は、 th ビットをシフトするときに、マスクされていない範囲の後n-1のビットがクリアであることを確認することによって、これが起こらないことを確認します)i-1i

...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予想されるすべて 1 の結果と比較します-1 << (64-n)(64 ビット符号なしの場合)。

ビットを抽出する魔法のシフト/乗算は、2 つが等しい場合にのみ機能します。

于 2013-01-27T20:14:15.567 に答える
14

この非常に興味深い質問に対する優れた回答に加えて、このビット単位の乗算のトリックが 2007 年以来コンピューター チェス コミュニティで知られており、Magic BitBoardsという名前で知られていることを知っておくと役立つかもしれません。

多くのコンピュータ チェス エンジンは、複数の 64 ビット整数 (ビットボードと呼ばれる) を使用して、さまざまなピース セット (占有される正方形ごとに 1 ビット) を表します。特定の元のマスにあるスライディング ピース (ルーク、ビショップ、クイーン) は、Kブロック ピースが存在しない場合、最大で 2 つのマスに移動できるとします。K占有された正方形のビットボードでこれらの散らばったビットのビット単位の AND を使用するとK、64 ビット整数内に埋め込まれた特定のビット ワードが得られます。

魔法の乗算を使用して、これらの分散ビットを64 ビット整数Kの下位ビットにマップできます。K次に、これらの下位Kビットを使用して、元の正方形のピースが実際に移動できる許可された正方形を表す、事前に計算されたビットボードのテーブルにインデックスを付けることができます (ピースをブロックするなどの処理を行います)。

このアプローチを使用する典型的なチェス エンジンには、事前に計算された結果を含む 64 エントリ (オリジン スクエアごとに 1 つ) の 2 つのテーブル (ルーク用に 1 つ、ビショップ用に 1 つ、両方の組み合わせを使用するクイーン) があります。現在、最高評価のクローズド ソース ( Houdini ) とオープン ソース チェス エンジン ( Stockfish ) の両方が、その非常に高いパフォーマンスのためにこのアプローチを使用しています。

これらの魔法の乗数を見つけるには、徹底的な検索(初期のカットオフで最適化) または試行錯誤(たとえば、多数のランダムな 64 ビット整数を試す) を使用します。魔法定数が見つからないムーブ生成時に使用されたビット パターンはありません。ただし、マップされるビットに (ほぼ) 隣接するインデックスがある場合、通常、ビットごとのキャリー効果が必要です。

私の知る限り、@Syzygy による非常に一般的な SAT ソルバー アプローチはコンピューター チェスでは使用されておらず、そのような魔法の定数の存在と一意性に関する正式な理論もないようです。

于 2013-04-14T12:00:35.823 に答える