13

Programming Pearls、2nd Editionの140ページで、Jonはビットベクトルを使用したセットの実装を提案しました。

ここで、セットが整数を表すという事実を利用する2つの最終的な構造に目を向けます。ビットベクトルは列1の古くからの友人です。これらのプライベートデータと関数は次のとおりです。

enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
int n, hi, *x;
void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i)  {        x[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i) { return x[i>>SHIFT] &=  (1<<(i & MASK)); }

私が集めたように、列1で説明したように、整数セットを表すビットベクトルの中心的な考え方は、整数iがセットに含まれている場合にのみ、i番目のビットがオンになることです。

しかし、私は上記の3つの機能に関係するアルゴリズムに本当に戸惑っています。そして、その本は説明をしていません。

私が得ることi & MASKができるのは、iの下位5ビットを取得することだけですが、 i>>SHIFTiを5ビット右に移動することです。

誰かがこれらのアルゴリズムについてもっと詳しく説明しますか？ビット演算は常に私には神話のように思えます:(

4

3 に答える 3

57

ビットフィールドとあなた

簡単な例を使って基本を説明します。4ビットの符号なし整数があるとします。

[0][0][0][0] = 0

ここでは、基数2に変換することで、0から15までの任意の数値を表すことができます。右端が最小であるとします。

[0][1][0][1] = 5

したがって、最初のビットは合計に1を加算し、2番目は2を加算し、3番目は4を加算し、4番目は8を加算します。たとえば、次は8です。

[1][0][0][0] = 8

だから何？ アプリケーションでバイナリ状態を表現したいとします。オプションが有効になっている場合、要素を描画する必要がある場合などです。これらのそれぞれに整数全体を使用することはおそらく望ましくありません。1ビットの情報を格納するために32ビット整数を使用することになります。または、例を4ビットで続けるには：

[0][0][0][1] = 1 = ON
[0][0][0][0] = 0 = OFF //what a huge waste of space!

（もちろん、32ビット整数は次のように見えるため、問題は実際にはより顕著になります。

[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0] = 0

これに対する答えは、ビットフィールドを使用することです。プロパティ（通常は関連するプロパティ）のコレクションがあり、ビット演算を使用してオンとオフを切り替えます。たとえば、オンまたはオフにしたいハードウェアに4つの異なるライトがあるとします。

 3  2  1  0
[0][0][0][0] = 0

（なぜライト0から始めるのですか？これについてはすぐに説明します。）これは整数であり、整数として格納されますが、複数のオブジェクトの複数の状態を表すために使用されることに注意してください。クレイジー！ライト2と1をオンにするとします。

 3  2  1  0
[0][1][1][0] = 6

ここで注意しなければならない重要なこと：ライト2と1が点灯している必要がある理由はおそらく明らかではなく、この情報ストレージのスキームでどのように処理するかは明らかではないかもしれません。さらにビットを追加した場合、それはより明白に見えません：

 3  2  1  0
[1][1][1][0] = 0xE \\what?

なぜ私たちはこれを気にするのですか？0から15までの数値ごとに正確に1つの状態がありますか？いくつかの非常識な一連のswitchステートメントなしでこれをどのように管理しますか？うーん...

最後の光

したがって、少し前に2進演算を使用したことがある場合は、左側の数値と右側の数値の関係は、もちろん2を底にしていることに気付くかもしれません。

1 *（2 3）+ 1 *（2 2）+ 1 *（2 1）+0 *（2 0）= 0xE

したがって、各ライトは方程式の各項の指数に存在します。ライトがオンの場合、その項の横に1があります。ライトがオフの場合、ゼロがあります。この番号付けスキームの各状態に対応する0から15までの整数が1つだけあることを、時間をかけて確信してください。

ビット演算子

これが完了したので、少し時間を取って、このセットアップで整数に対してビットシフトがどのように行われるかを見てみましょう。

[0][0][0][1] = 1

ビットを整数で左または右にシフトすると、文字通りビットが左右に移動します。（注：負の数については、この説明を100％否認します！ドラゴンがいます！）

1<<2 = 4
[0][1][0][0] = 4
4>>1 = 2
[0][0][1][0] = 2

複数のビットで表される数値をシフトすると、同様の動作が発生します。また、x>>0またはx<<0は単なるxであると自分自身に納得させるのは難しいことではありません。どこにもシフトしません。

これはおそらく、シフト演算子の命名スキームを、それらに精通していない人に説明しています。

ビット演算

この2進数の数値表現は、整数のビット演算子の操作に光を当てるためにも使用できます。最初の番号の各ビットは、その仲間の番号とxor-ed、and-ed、またはor-edされます。少し時間を取ってウィキペディアに足を運び、これらのブール演算子の機能に慣れてください。これらが数値でどのように機能するかを説明しますが、一般的な考え方を詳細に再ハッシュしたくありません。

..。

お帰りなさい！4ビットに格納された2つの整数に対するOR（|）演算子の効果を調べることから始めましょう。

 OR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][1][0][1] = 0xD

タフ！これは、ブールOR演算子の真理値表によく似ています。各列は隣接する列を無視し、結果列に最初のビットと2番目のビットの結果をORで埋めるだけであることに注意してください。また、その特定の列では、or'dの値が1であることに注意してください。ゼロの場合は何でも同じままです。

AND（＆）の表は興味深いものですが、多少逆になっています。

 AND OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][0][0][0] = 0x8

この場合、同じことを行います。列の各ビットでAND演算を実行し、結果をそのビットに入れます。他の列を気にする列はありません。

これに関する重要な教訓。上の図を使用して確認することをお勧めします。ゼロでAND演算されたものはすべてゼロです。また、同様に重要です。1とAND演算された数値には何も起こりません。彼らは同じままです。

ファイナルテーブルのXORには、皆さんが今までに予測できると思う動作があります。

 XOR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [0][1][0][1] = 0x5

各ビットは、その列、yaddayaddaなどとXORされています。しかし、最初の行と2番目の行をよく見てください。どのビットが変更されましたか？（それらの半分。）どのビットが同じままでしたか？（これに答えるポイントはありません。）

2番目の行のビットが1の場合（そしてその場合のみ）、結果の最初の行のビットが変更されます。

1つの電球の例！

これで、個々のビットを反転するために使用できる興味深いツールのセットができました。電球の例に戻り、最初の電球だけに焦点を当てましょう。

 0
[?] \\We don't know if it's one or zero while coding

このビットを常に1に等しくすることができる演算（OR 1演算子）があることはわかっています。

0|1 = 1
1|1 = 1

したがって、残りの電球を無視すると、これを行うことができます

4_bit_lightbulb_integer | = 1;

そして、最初の電球をオンに設定する以外に何もしなかったことを確実に知っています。

 3  2  1  0
[0][0][0][?] = 0 or 1? \\4_bit_lightbulb_integer
[0][0][0][1] = 1
________________
[0][0][0][1] = 0x1

同様に、数値をゼロとANDすることができます。ゼロではありませんが、他のビットの状態に影響を与えたくないので、ビットを1で埋めます。

ビット否定には単項（1引数）演算子を使用します。〜（NOT）ビット演算子は、引数のすべてのビットを反転します。〜（0X1）：

[0][0][0][1] = 0x1
________________
[1][1][1][0] = 0xE

これを以下のANDビットと組み合わせて使用​​します。

4_bit_lightbulb_integer＆0xEをやってみましょう

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[1][1][1][0] = 0xE
________________
[0][1][0][0] = 0x4

右側に多くの整数が表示されていますが、これらは直接の関連性はありません。ビットフィールドをたくさん扱う場合は、これに慣れる必要があります。左側を見てください。右側のビットは常にゼロであり、他のビットは変更されていません。ライト0をオフにして、他のすべてを無視することができます。

最後に、XORビットを使用して、最初のビットを選択的に反転できます。

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[0][0][0][1] = 0x1
________________
[0][1][0][*] = 4 or 5?

*の値が現在何であるかは実際にはわかりません-それは何からでも反転しただけですか？だった。

ビットシフト演算とビット演算の組み合わせ

これらの2つの操作に関する興味深い事実は、これらを組み合わせると、選択ビットを操作できるようになることです。

[0][0][0][1] = 1 = 1<<0
[0][0][1][0] = 2 = 1<<1
[0][1][0][0] = 4 = 1<<2
[1][0][0][0] = 8 = 1<<3

うーん。面白い。ここで否定演算子（〜）について説明します。これは、ビットフィールドのAND処理に必要なビット値を生成するために同様の方法で使用されるためです。

[1][1][1][0] = 0xE = ~(1<<0)
[1][1][0][1] = 0xD = ~(1<<1)
[1][0][1][1] = 0xB = ~(1<<2)
[0][1][1][1] = 0X7 = ~(1<<3)

シフト値とシフトされたビットの対応する電球の位置の間に興味深い関係が見られますか？

正規のビットシフト演算子

上記で示唆したように、上記のビットシフターを使用して特定のライトをオンまたはオフにするための興味深い一般的な方法があります。

電球をオンにするには、ビットシフトを使用して正しい位置に1を生成し、それを現在の電球の位置とORします。ライト3をオンにし、それ以外はすべて無視するとします。ORを実行するビットシフト操作を取得する必要があります

 3  2  1  0
[?][?][?][?]  \\all we know about these values at compile time is where they are!

および0x8

[1][0][0][0] = 0x8

ビットシフトのおかげで、これは簡単です！ライトの番号を選択し、値を切り替えます。

1<<3 = 0x8

その後：

4_bit_lightbulb_integer |= 0x8;

 3  2  1  0
[1][?][?][?]  \\the ? marks have not changed!

そして、3番目の電球のビットが1に設定され、他に何も変更されていないことを保証できます。

ビットのクリアも同様に機能します。たとえば、上記の否定ビットの表を使用して、ライト2をクリアします。

~(1<<2) = 0xB = [1][0][1][1]

4_bit_lightbulb_integer＆0xB：

 3  2  1  0
[?][?][?][?] 
[1][0][1][1]
____________
[?][0][?][?]

ビットを反転するXOR方式は、OR方式と同じ考え方です。

したがって、ビットスイッチングの標準的な方法は次のとおりです。

ライトをオンにします。

4_bit_lightbulb_integer|=(1<<i)

ライトをオフにするi：

4_bit_lightbulb_integer&=~(1<<i)

フリップライトi：

4_bit_lightbulb_integer^=(1<<i)

待って、どうやってこれらを読むの？

ビットをチェックするために、気になるビットを除くすべてのビットを単純にゼロにすることができます。次に、結果の値がゼロより大きいかどうかを確認します。これはゼロ以外になる可能性がある唯一の値であるため、ゼロ以外の場合に限り、整数全体がゼロ以外になります。たとえば、ビット2をチェックします。

1 << 2：

[0][1][0][0]

4_bit_lightbulb_integer：

[?][?][?][?]

1 << 2＆4_bit_lightbulb_integer：

[0][?][0][0]

前の例から、？の値が 変わらなかった。また、AND 0は0であることに注意してください。したがって、この値がゼロより大きい場合、位置2のスイッチは真であり、電球はゼロであると確実に言えます。同様に、値がオフの場合、全体の値はゼロになります。

（4_bit_lightbulb_integerの値全体をiビットずつシフトし、1とANDすることもできます。一方が他方よりも速いかどうかは頭のてっぺんから覚えていませんが、疑わしいです。）

したがって、正規のチェック機能は次のとおりです。

ビットiがオンになっているかどうかを確認します。 

if (4_bit_lightbulb_integer & 1<<i) {
\\do whatever

}

詳細

ビット演算用のツールの完全なセットができたので、ここで特定の例を見ることができます。これは基本的に同じ考えです-それを実行するはるかに簡潔で強力な方法を除いて。この関数を見てみましょう：

void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }

正規の実装から、これがいくつかのビットを1に設定しようとしていると推測します。整数を取り、値0x32（10進数で50）をiにフィードした場合にここで何が起こっているかを見てみましょう：

x[0x32>>5] |= (1<<(0x32 & 0x1f))

さて、それは混乱です..右側でこの操作を分析しましょう。便宜上、これらは両方とも32ビット整数であるため、24個の無関係なゼロがあると仮定します。

...[0][0][0][1][1][1][1][1] = 0x1F
...[0][0][1][1][0][0][1][0] = 0x32
________________________
...[0][0][0][1][0][0][1][0] = 0x12

1がゼロに変わる上部の境界ですべてが切断されているように見えます。この手法はビットマスキングと呼ばれます。興味深いことに、ここでの境界は、結果の値を0から31の間に制限します...これは、32ビット整数のビット位置の数とまったく同じです。

x [0x32 >> 5] | =（1 <<（0x12））残りの半分を見てみましょう。

...[0][0][1][1][0][0][1][0] = 0x32

5ビットを右にシフトします。

...[0][0][0][0][0][0][0][1] = 0x01

この変換により、関数の最初の部分からすべての情報が正確に破壊されたことに注意してください。残りのビットは32-5 = 27であり、ゼロ以外の可能性があります。これは、整数の配列内の227個の整数のどれが選択されているかを示します。したがって、簡略化された方程式は次のようになります。

x[1] |= (1<<0x12)

これは、標準的なビット設定操作のように見えます。選択しました

したがって、最初の27ビットを使用してシフトする整数を選択し、最後の5ビットはその整数の32のどのビットをシフトするかを示します。

于 2012-07-09T18:28:23.360 に答える
12

何が起こっているのかを理解するための鍵は、それを認識することですBITSPERWORD=2 SHIFT。したがって、x[i>>SHIFT]配列のどの32ビット要素がにx対応するビットを持っているかを見つけiます。（5ビットを右にシフトiすると、単純に32で除算されます。）の正しい要素を見つけたらx、の下位5ビットをi使用して、のどの特定のビットがにx[i>>SHIFT]対応するかを見つけることができますi。それが何をするかi & MASKです。1をそのビット数だけシフトすることにより、1に対応するビットを、のthビットにx[i>>SHIFT]対応する正確な位置に移動します。ix

ここにもう少し説明があります：

Nビットベクトルのビット容量が必要だと想像してください。それぞれintが32ビットを保持する(N + 31) / 32 intため、ストレージの値が必要になります（つまり、N / 32は切り上げられます）。各int値の中で、ビットは最下位から最上位の順に並べられるという規則を採用します。また、ベクトルの最初の32ビットがにx[0]あり、次の32ビットがにあるという規則を採用x[1]します。使用しているメモリレイアウトは次のとおりです（メモリの各ビットに対応するビットベクトルのビットインデックスを示しています）。

      +----+----+-------+----+----+----+
x[0]: | 31 | 30 | . . . | 02 | 01 | 00 |
      +----+----+-------+----+----+----+
x[1]: | 63 | 62 | . . . | 34 | 33 | 32 |
      +----+----+-------+----+----+----+
        etc.

最初のステップは、必要なストレージ容量を割り当てることです。

x = new int[(N + BITSPERWORD - 1) >> SHIFT]

（このストレージを動的に拡張するためのプロビジョニングを行うこともできますが、それでは説明が複雑になります。）

ここで、ビットにアクセスしたいとしますi（ビットを設定するか、クリアするか、または単に現在の値を知るために）。まず、のどの要素xを使用するかを理解する必要があります。値ごとに32ビットがあるためint、これは簡単です。

subscript for x = i / 32

列挙型定数を利用して、x必要な要素は次のとおりです。

x[i >> SHIFT]

（これを、Nビットベクトルへの32ビット幅のウィンドウと考えてください。）次に、に対応する特定のビットを見つける必要がありますi。メモリレイアウトを見ると、ウィンドウの最初の（右端の）ビットがビットインデックスに対応していることを理解するのは難しくありません32 * (i >> SHIFT)。（ウィンドウはi >> SHIFTスロットの後に始まりx、各スロットには32ビットがあります。）これはウィンドウの最初のビット（位置0）であるため、関心のあるビットは位置にあります。

i - (32 * (i >> SHIFT))

窓に。少し実験するだけで、この式は常に等しいi % 32（実際には、これはmod演算子の1つの定義です）、つまり常に等しいことを確信できますi & MASK。この最後の式は、必要なものを計算するための最速の方法であるため、これを使用します。

ここから、残りはかなり簡単です。ウィンドウの最下位位置にある1ビット（つまり、定数1）から始めて、ビットだけ左に移動し、ビットベクトルのi & MASKビットに対応するウィンドウ内の位置に移動します。iこれは、式がどこにあるかです

1 << (i & MASK)

から来た。ビットが目的の場所に移動したので、これをマスクとして使用して、のその位置にあるビットの値をx[i>>SHIFT]設定、クリア、またはクエリできます。実際に値を設定、クリア、またはクエリしていることがわかります。i私たちのビットベクトルのビットの。

于 2012-07-09T17:45:01.583 に答える
4

ビットをn 単語nの配列に格納すると、それらが行と32列の行列としてレイアウトされることを想像できます（ BITSPERWORD）：

         3                                         0
         1                                         0
      0  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      1  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx
      2  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx     
      ....
      n  xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx

k番目のビットを取得するには、kを32で除算します。（整数）の結果により、ビットが含まれている行（ワード）がわかり、リマインダーにより、ワード内にあるビットがわかります。

分割は、位置を右に2^pシフトするだけで実行できます。pリマインダーは、p個の右端のビットを取得することで取得できます（つまり、ビット単位のANDと（2 ^ p-1））。

C用語で：

#define div32(k) ((k) >> 5)
#define mod32(k) ((k) & 31)

#define word_the_bit_is_in(k) div32(k)
#define bit_within_word(k)    mod32(k)

それが役に立てば幸い。

于 2012-07-09T18:18:37.303 に答える