非常に興味深い質問であり、巧妙なトリックです。
単一バイトを操作する簡単な例を見てみましょう。簡単にするために符号なし 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 つ増やします。
上記に従うことで、あなたの答えに長い道のりが得られると思います...