[解決済み】1回の乗算でビットを抽出する方法

質問

で使われている面白いテクニックを見ました。 回答 を使用します。 別の質問 もう少し理解したい。

64ビットの符号なし整数が与えられ、以下のビットに興味があります。

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

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

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

で示されるビットの値は気にしない。 . であり、保存する必要はない。

は 解決策 は、不要なビットをマスクし、その結果に 0x2040810204081 . これで、結果的にうまくいった。

この方法はどの程度汎用性があるのでしょうか？この技法はビットの任意の部分集合を抽出するために使用できるのでしょうか？そうでない場合、この方法が特定のビットの集合に対して有効かどうかをどのように判断するのでしょうか？

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

どのように解決するのか？

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

1バイトを操作させる簡単な例を見てみましょう。簡単のために符号なし8ビットを使用します。例えば、次のような数字があるとします。 xxaxxbxx を必要とし ab000000 .

解決策は、ビットマスクと乗算の2つのステップで構成されています。ビットマスクは単純なAND演算で、興味のないビットを0にするものです。上記の場合、マスクは次のようになります。 00100100 となり、その結果 00a00b00 .

さて、難しいのは、これを ab...... .

乗算は、シフトと加算の演算の束です。重要なのは、オーバーフローによって不要なビットを"shift away"し、必要なビットを適切な場所に配置することです。

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

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

この方法から、より大きな数、より多くのビットに拡張することができます。

マスキングや乗算を何度か行わない限り、答えは「ノー」だと思います。問題は衝突の問題で、例えば上の問題では「迷子のb」があります。例えば、上の問題で言えば、「迷子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個のゼロが必要で、右側にn-m個のゼロが必要なのです。特に、ビットの並びが元の数と並び替え後の数で同じでない場合、これは元の基準に対する重要な改善点です。これは、例えば16ビットワードが

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

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

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

eとbの間に1つ、dとcの間に2つ、その他の間に3つのスペースがあるだけなのに。N-1はどうしたんだ？この場合 a...e は1ブロックになり、1倍されて正しい場所に配置されるため、quot;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) または、最終結果のビットの順序がわかっている場合、ビットbがnのm番目の位置で終わるなら、その左側にm-1個のゼロがあり、右側にn-m個のゼロが必要です。

このルールがうまく機能しないのは、quot;ターゲット領域のすぐ右側を追加するビットからのキャリーがあるため、つまり、探しているビットがすべて1である場合だと@Ternaryは指摘しています。先ほどの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) 位置 G にビットがキャリーされます。 F ということになります。 (d+1) 位置 F に少し持ち越すことになります。 E - となり、結果が台無しになります。最下位ビットの右側にあるスペースに注意してください ( c この例では、乗算によって最下位ビットより後ろがゼロでパディングされるため、重要ではありません。

そこで、(m-1)/(n-m)のルールを修正する必要があります。もし、右側に "ちょうど (n-m) 個の未使用ビットがある場合（パターンの最後のビット - 上の例では "c" を除く）、ルールを強化する必要があります - そしてそれを繰り返し行う必要があります！(m-1) / (n-m) ルールを修正する必要があります。

(n-m)の基準を満たすビットの数だけでなく、(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 それでもダメなら、基準をもう一つ増やす、など。

以上のことを守れば、答えまでの道のりは遠いと思うのですが...。