1回の乗算でビットを抽出する質問する

Question

とても興味深い質問であり、巧妙なトリックです。

1 バイトを操作する簡単な例を見てみましょう。簡単にするために、符号なし 8 ビットを使用します。数値がでxxaxxbxx、が欲しいとしますab000000。

解決策は、ビットマスクとそれに続く乗算の 2 つのステップで構成されます。ビットマスクは、不要なビットをゼロにする単純な AND 演算です。上記のケースでは、マスクはになり、00100100結果はになります00a00b00。

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

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

4 ( 00000100) を掛けると、すべてが 2 左にシフトし、になりますa00b0000。を上に移動するには、b1 (a を正しい位置に保つため) + 4 (b を上に移動するため) を掛ける必要があります。この合計は 5 で、前の 4 と組み合わせると、魔法の数字 20、つまりが得られます00010100。オリジナルは00a00b00マスク後のもので、掛け算は次のようになります。

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

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

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

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

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

したがって、正式な証明はなくても、質問のより興味深い部分に次のように答えます。「いいえ、これは任意のビット数では機能しません。N ビットを抽出するには、抽出するビット間に (N-1) 個のスペースが必要です。または、追加のマスク乗算手順が必要です。」

「ビット間には (N-1) 個のゼロがなければならない」というルールに関して私が考えられる唯一の例外は、元のデータで互いに隣接している 2 つのビットを抽出し、それらを同じ順序で維持したい場合、それを実行できるということです。また、(N-1) ルールの目的上、それらは 2 つのビットとしてカウントされます。

もう一つの洞察があります。下の @Ternary の回答に触発されたものです (私のコメントを参照してください)。各関心のあるビットについて、その右側には、そこに配置する必要があるビットのスペースと同じ数のゼロが必要です。ただし、左側には、結果ビットと同じ数のビットが必要です。したがって、ビット b が n の m の位置になった場合、その左側には m-1 個のゼロ、右側には nm 個のゼロが必要です。特に、ビットが元の番号と並べ替え後の順序が同じでない場合は、これは元の基準に対する重要な改善です。つまり、たとえば、16 ビットのワード

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

シフト可能

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

e と b の間にはスペースが 1 つしかなく、d と c の間にはスペースが 2 つ、他の 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 が n の m 番目の位置になる場合、その左側に m-1 個のゼロ、右側に nm 個のゼロが必要です。」

@Ternary は、このルールはうまくいかないと指摘しました。「ターゲット領域のすぐ右側」にビットを追加すると、つまり、探しているビットがすべて 1 の場合に、桁上がりが発生する可能性があるからです。16 ビットワードに 5 つのビットが密集している例を続けます。

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)GF(d+1)FEc

したがって、(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 つ増やします。

上記の手順に従うと、答えにかなり近づくと思います...

Answer 1