ビット演算

コンピュータプログラミング では、ビット演算は、ビット列、ビット配列、または2 進数値(ビット列と見なされる) を個々のビットのレベルで操作します。これは高速で単純なアクションであり、高レベルの算術演算の基本であり、プロセッサによって直接サポートされています。ほとんどのビット演算は、結果が入力オペランドの 1 つを置き換える 2 つのオペランド命令として表されます。

シンプルで低コストのプロセッサでは、通常、ビット演算は除算よりも大幅に高速で、乗算よりも数倍高速で、場合によっては加算よりも大幅に高速です。現代のプロセッサは、命令パイプラインが長くなったり、その他のアーキテクチャ設計の選択により、通常、加算と乗算をビット演算と同じくらい高速に実行しますが、ビット演算ではリソースの使用が減るため、一般的に消費電力が少なくなります。^[1]

以下の説明では、ビットの位置を示す場合は、右側 (最下位) から左に進んで数えます。たとえば、2 進数値 0001 (10 進数値 1) には、最初の位置 (つまり、右端) を除くすべての位置にゼロがあります。

ビット単位の NOT、またはビット単位の補数は、各ビットの論理否定を実行し、指定された 2 進値の1 の補数を形成する単項演算です。0 のビットは 1 になり、1 のビットは 0 になります。例:

0 111ではない(10進数の 7)
  = 1 000 (10進数8)

10101011 ではない (10 進数 171)
  = 01010100 (10進数では84)

結果は、値から 1 を引いた値の2 の補数に等しくなります。2 の補数演算を使用する場合は、次のようになりますNOT x = -x − 1。

符号なし整数の場合、数値のビットごとの補数は、符号なし整数の範囲の中間点を挟んだ数値の「鏡映し」です。たとえば、8 ビットの符号なし整数 の場合、NOT x = 255 - xこれは、0 から 255 までの増加範囲を 255 から 0 まで減少範囲に効果的に「反転」する下向きの線としてグラフ上で視覚化できます。単純ですがわかりやすい使用例としては、各ピクセルが符号なし整数として保存されているグレースケール画像を反転することが挙げられます。

ビットAND は、2 つの等長バイナリ表現を受け取り、対応するビットの各ペアに対して論理 AND演算を実行するバイナリ演算です。したがって、比較位置の両方のビットが 1 の場合、結果のバイナリ表現のビットは 1 (1 × 1 = 1) になります。それ以外の場合、結果は 0 (1 × 0 = 0 および 0 × 0 = 0) になります。例:

    010 1 (10進数5)
AND 001 1 (10進数3)
  = 000 1 (10進数の1)

この演算は、特定のビットが設定されている(1) か、クリアされている(0) かを判断するために使用できます。たとえば、ビット パターン 0011 (10 進数で 3) が与えられた場合、2 番目のビットが設定されているかどうかを判断するには、2 番目のビットにのみ 1 を含むビット パターンとのビット単位の AND を使用します。

    00 1 1 (10進数3)
AND 00 1 0 (10進数2)
  = 00 1 0 (10進数2)

結果 0010 はゼロではないため、元のパターンの 2 番目のビットが設定されていることがわかります。これは、ビット マスキングと呼ばれることがよくあります。(類推すると、マスキング テープを使用すると、変更してはいけない部分や重要でない部分をカバー (マスク) できます。この場合、0 の値は重要でないビットをマスクします。)

ビット単位の AND は、各ビットが個別のブール状態を表すレジスタの選択されたビット (またはフラグ)をクリアするために使用できます。この手法は、可能な限り少ないメモリを使用して多数のブール値を格納する効率的な方法です。

たとえば、0110 (10 進数の 6) は、右から左に番号が付けられた 4 つのフラグのセットと見なすことができます。この場合、1 番目と 4 番目のフラグはクリア (0) され、2 番目と 3 番目のフラグはセット (1) されます。3 番目のフラグは、3 番目のビットにのみ 0 が含まれるパターンとのビット単位の AND を使用してクリアできます。

    0 1 10 (10進数6)
AND 1 0 11 (10進数の11)
  = 0 0 10 (10進数2)

この特性により、最も低い値のビットの値をチェックすることで、2 進数の パリティを簡単にチェックできるようになります。上記の例を使用すると、次のようになります。

    0110 (10進数6)
AND 0001 (10進数1)
  = 0000 (10進数の0)

6 AND 1 は 0 なので、6 は 2 で割り切れ、したがって偶数です。

ビットOR は、同じ長さの 2 つのビット パターンを受け取り、対応するビットの各ペアに対して論理的包含 OR演算を実行するバイナリ演算です。両方のビットが 0 の場合、各位置の結果は 0 になり、それ以外の場合は 1 になります。例:

   0 101 (10進数5)
または 0 011 (10進数3)
 = 0 111 (10進数7)

ビット単位の OR は、上記のレジスタの選択されたビットを 1 に設定するために使用できます。たとえば、0010 (10 進数では 2) の 4 番目のビットは、4 番目のビットのみが設定されたパターンでビット単位の OR を実行することによって設定できます。

   0 0 1 0 (10進数2)
または1 0 0 0 (10進数8)
 = 1 0 1 0 (10進数の10)

ビット単位の XOR は、長さが同じ 2 つのビット パターンを受け取り、対応するビットの各ペアに対して論理排他的 OR演算を実行するバイナリ演算です。各位置の結果は、ビットの 1 つだけが 1 の場合は 1 になりますが、両方が 0 または両方が 1 の場合は 0 になります。この演算では、2 つのビットを比較し、2 つのビットが異なる場合は 1、同じ場合は 0 になります。例:

    0 10 1 (10進数5)
XOR 0 01 1 (10進数3)
  = 0 11 0 (10進数6)

ビット単位の XOR は、レジスタ内の選択したビットを反転するために使用できます (トグルまたはフリップとも呼ばれます)。任意のビットを 1 と XOR することでトグルできます。たとえば、ビット パターン 0010 (10 進数で 2) の場合、2 番目と 4 番目のビットは、2 番目と 4 番目の位置に 1 を含むビット パターンとのビット単位の XOR によってトグルできます。

    0 0 1 0 (10進数2)
XOR 1 0 1 0 (10進数10)
  = 1 0 0 0 (10進数8)

この手法は、ブール状態のセットを表すビット パターンを操作するために使用できます。

アセンブリ言語プログラマーや最適化コンパイラーは、レジスタの値をゼロに設定するためのショートカットとして XOR を使用する場合があります。値に対して XOR を実行すると、常にゼロが生成されます。また、多くのアーキテクチャーでは、この操作に必要なクロック サイクルとメモリは、ゼロ値をロードしてレジスタに保存するよりも少なくなります。

固定長nのビット文字列の集合(つまりマシンワード) を体上のn次元ベクトル空間 と考えると、ベクトルの加算はビット単位の XOR に対応します。 ${\displaystyle {\bf {F}}_{2}^{n}}$ ${\displaystyle {\bf {F}}_{2}}$

⁠ ⁠${\displaystyle x\geq y}$と仮定すると、非負の整数に対して、ビット演算は次のように記述できます。

${\displaystyle {\begin{aligned}\operatorname {NOT} x&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]=2^{\left\lfloor \log _{2}(x)\right\rfloor +1}-1-x\\x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)-\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right)\\x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right]\end{aligned}}}$

2 つのバイナリ変数には 16 個の可能な真理関数があり、これが真理値表を定義します。

以下は、2 つのビット P と Q のビット単位の等価演算です。

ビットシフトは、値を数値ではなく一連のビットとして扱うため、ビット単位の操作と見なされることがあります。これらの操作では、数字が左または右に移動、つまりシフトされます。コンピュータ プロセッサのレジスタの幅は固定されているため、一部のビットはレジスタの一方の端から「シフト アウト」され、同じ数のビットがもう一方の端から「シフト イン」されます。ビット シフト演算子間の違いは、シフト インされたビットの値を決定する方法にあります。

レジスタの幅 (多くの場合 32 または 64) が、バイトと呼ばれる最小のアドレス指定単位のビット数 (通常は 8) よりも大きい場合、シフト操作によってバイトからビットへのアドレス指定スキームが誘導されます。これにより、「左」と「右」の方向は、位取り記法での数値の標準的な書き方から取得され、左シフトでは数値が増加し、右シフトでは数値が減少します。左の桁が最初に読み取られる場合、これはビッグエンディアン方向を構成します。レジスタの両端の境界効果を無視すると、算術シフト操作と論理シフト操作は同じ動作をし、8 ビット位置のシフトは、次のようにビット パターンを 1 バイト位置だけ転送します。

算術シフトでは、どちらかの端からシフトされたビットは破棄されます。左算術シフトでは、ゼロが右側にシフトされ、右算術シフトでは、符号ビット(2 の補数の MSB) が左側にシフトされるため、オペランドの符号が保持されます。

この例では、2 の補数として解釈される 8 ビット レジスタを使用します。

   00010111 (10進数 +23) 左シフト
= 0010111 0 (10進数 +46)

   10010111 (10進数 -105) 右シフト
=   1 1001011 (10進数 -53)

最初のケースでは、左端の桁がレジスタの末尾を超えてシフトされ、新しい 0 が右端の位置にシフトされました。2 番目のケースでは、右端の 1 がシフトアウトされ (おそらくキャリー フラグに)、新しい 1 が左端の位置にコピーされ、数値の符号が保持されます。複数のシフトは、いくつかの桁による 1 回のシフトに短縮されることがあります。例:

   00010111 (10進数 +23) 左シフト2
= 010111 00 (10進数 +92)

nの左算術シフトは2 ⁿを掛けることと同等です(値がオーバーフローしない場合)。一方、2 の補数値のnの右算術シフトは 2 ⁿによる除算の切り捨てと同等です。2 進数が1 の補数として扱われる場合、同じ右シフト演算は 2 ⁿによる除算となり、ゼロに向かって丸められます。

論理シフトでは、破棄されたビットを置き換えるためにゼロがシフトされます。したがって、論理左シフトと算術左シフトはまったく同じです。

ただし、論理右シフトは、符号ビットをコピーする代わりに、最上位ビットに値 0 ビットを挿入するため、符号なしの 2 進数には最適ですが、算術右シフトは、符号付きの2 の補数 2進数には最適です。

シフトの別の形式は、循環シフト、ビット回転、またはビット回転です。

この操作は、ローテート ノー キャリーとも呼ばれ、レジスタの左端と右端が結合されたかのようにビットが「回転」します。左シフト中に右にシフトされる値は、左にシフトアウトされた値であり、右シフト操作の場合はその逆です。これは、既存のビットをすべて保持する必要がある場合に便利で、デジタル暗号化でよく使用されます。^{[説明が必要]}

キャリーによる回転は回転操作の変形であり、シフトインされるビット (どちらかの端) はキャリー フラグの古い値になり、シフトアウトされるビット (もう一方の端) はキャリー フラグの新しい値になります。

キャリー フラグを事前に設定しておくことで、1 回のローテーション スルー キャリーでx RIGHT-ROTATE-THROUGH-CARRY-BY-ONE1 つの位置の論理シフトまたは算術シフトをシミュレートできます。たとえば、キャリー フラグに 0 が含まれている場合は、論理右シフトになり、キャリー フラグに符号ビットのコピーが含まれている場合は、x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE算術右シフトになります。このため、ローエンドのPICなどの一部のマイクロコントローラでは、ローテーションとローテーション スルー キャリーのみが用意されており、算術シフトまたは論理シフト命令は使用されません。

回転キャリーは、プロセッサのネイティブワード サイズよりも大きい数値のシフトを実行するときに特に便利です。これは、大きな数値が 2 つのレジスタに格納されている場合、最初のレジスタの一方の端からシフトされたビットが、2 番目のレジスタのもう一方の端から入らなければならないためです。回転キャリーでは、そのビットは最初のシフト中にキャリー フラグに「保存」され、追加の準備なしで 2 番目のシフト中にシフトインする準備が整います。

C および C++ 言語では、論理シフト演算子は<<左シフトの場合は " "、>>右シフトの場合は " " です。シフトする桁数は、演算子の 2 番目の引数として指定します。たとえば、

yは0です。​    

2 ビット左に xシフトした結果を割り当てます。これは 4 倍の乗算に相当します。y

シフトは実装定義の動作または未定義の動作を引き起こす可能性があるため、使用時には注意が必要です。ワードのサイズ以上のビット数でシフトした結果は、CおよびC++では未定義の動作です。^{[2] [3]}負の値を右シフトすることは実装定義であり、適切なコーディング方法では推奨されません。^[4]符号付きの値を左シフトした結果は、結果が結果の型で表現できない場合は未定義です。^[2]

C#では、最初のオペランドがintまたはlongの場合、右シフトは算術シフトです。最初のオペランドがuintまたはulong型の場合、右シフトは論理シフトです。^[5]

C言語ファミリーには回転演算子がない（ただしC++20ではstd::rotlと が提供される）が、シフト演算子から合成することができる。セキュリティ要件のあるソフトウェアでは、未定義の動作やタイミング攻撃をstd::rotr回避するために、ステートメントが適切に構成されていることを確認する必要がある。^[6]たとえば、32ビットの符号なし値を位置で左回転する単純な実装は、単に xn

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( 32 - n ));      
           

しかし、0ビットシフトを行うと、右辺の式は未定義の動作になります。(x >> (32 - n))なぜなら、32 - 0は であり32、32は 0～31の範囲外だからです。2回目の試行では、

uint32_t x = ..., n = ...; uint32_t y = n ? ( x << n ) | ( x >> ( 32 - n )) : x ;      
               

ここで、シフト量は未定義の動作をもたらさないことを確認するためにテストされます。しかし、分岐によって追加のコードパスが追加され、タイミング分析と攻撃の機会が生まれます。これは、高信頼性ソフトウェアでは許容されないことがよくあります。^[6]さらに、コードは複数のマシン命令にコンパイルされますが、これはプロセッサのネイティブ命令よりも効率が悪いことがよくあります。

GCCとClangでの未定義の動作と分岐を回避するには、次の方法が推奨されます。このパターンは多くのコンパイラで認識され、コンパイラは単一の回転命令を出力します。^{[7] [8] [9]}

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( - n & 31 ));      
           

Microsoft Visual C++の_rotl8、_rotl16、_rotr8、_rotr16のように、循環シフトを実装するコンパイラ固有の組み込み関数もあります。Clangは、上記の問題を抱えるMicrosoft互換性のために、回転組み込み関数をいくつか提供しています。^[9] GCCは回転組み込み関数を提供していません。Intelもx86組み込み関数を提供しています。

Java では、すべての整数型は符号付きなので、「<<」および「>>」演算子は算術シフトを実行します。Java では、論理右シフトを実行するために演算子「 」が追加されていますが、符号付き整数の場合、論理左シフト演算と算術左シフト演算は同じであるため、 Java には「 」演算子は >>>ありません。<<<

Javaシフト演算子の詳細: ^[10]

• 演算子<<(左シフト)、>>(符号付き右シフト)、 (符号なし右シフト) はシフト演算子>>>と呼ばれます。
• シフト式の型は、左側のオペランドの昇格された型です。たとえば、aByte >>> 2は と同等です。((int) aByte) >>> 2
• 左側のオペランドの昇格された型がintの場合、右側のオペランドの下位5ビットのみがシフト距離として使用されます。これは、右側のオペランドがマスク値0x1f（0b11111）を持つビット単位の論理AND演算子＆にかけられたのと同じです。^[11]したがって、実際に使用されるシフト距離は常に0から31の範囲です。
• 左側のオペランドの昇格された型がlongの場合、右側のオペランドの最下位6ビットのみがシフト距離として使用されます。これは、右側のオペランドがマスク値0x3f（0b111111）を持つビット単位の論理AND演算子＆にかけられたのと同じです。^[11]したがって、実際に使用されるシフト距離は常に0〜63の範囲になります。
• の値は、ゼロ拡張を使用してn右シフトされたsn >>> sビット位置です。
• ビット演算およびシフト演算では、型はbyte暗黙的に に変換されますint。バイト値が負の場合、最上位ビットは 1 で、int 内の余分なバイトを埋めるために 1 が使用されます。したがって、結果は になります。byte b1 = -5; int i = b1 | 0x0200;i == -5

JavaScriptはビット演算を使用して、2つ以上の単位のそれぞれを1または0に評価します^。[12]

Pascal およびそのすべての方言 ( Object PascalやStandard Pascalなど) では、論理左シフト演算子と論理右シフト演算子はそれぞれ " shl" と " shr" です。符号付き整数の場合でも、shr論理シフトのように動作し、符号ビットはコピーされません。シフトする桁数は、2 番目の引数として指定されます。たとえば、次の例では、y を2 ビット左に シフトした結果がx に割り当てられます。

x := y shl 2 ;    

• popcount、暗号化に使用される
• 先頭のゼロを数える

ビット演算は、デバイス ドライバー、低レベル グラフィックス、通信プロトコル パケットのアセンブリ、デコードなどの低レベル プログラミングでは特に必要です。

マシンには算術演算や論理演算を実行するための効率的な組み込み命令が備わっていることが多いが、これらの演算はすべて、ビット演算子とゼロテストをさまざまな方法で組み合わせることで実行できる。^[13] たとえば、ビットシフトと加算のみを使用して、任意の2つの整数と（より大きい）を乗算する方法を示す古代エジプトの乗算の疑似コード実装を次に示します。 abab

c ← 0、b ≠ 0の場合( b and 1 ) ≠ 0の場合c ← c + a aを1左シフト、bを1右シフト、c を返す  
   
         
            
        
        
 

もう 1 つの例は、ビット演算子とゼロ テストを使用して 2 つの整数の合計を計算する方法を示すa、加算の疑似コード実装です。b

a ≠ 0の場合c ← bかつa b ← b xor a を左にシフトcを1 だけシフトa ← c bを返す   
        
        
        
      
 

コンパイラを作成する場合など、ビット演算で構成される複雑な式を簡略化すると便利な場合があります。コンパイラの目的は、高水準プログラミング言語を可能な限り最も効率的なマシン コードに変換することです。ブール代数は、複雑なビット演算式を簡略化するために使用されます。

• x & y = y & x
• x & (y & z) = (x & y) & z
• x & 0xFFFF = x^[14]
• x & 0 = 0

• x & x = x

• x | y = y | x
• x | (y | z) = (x | y) | z
• x | 0 = x
• x | 0xFFFF = 0xFFFF
• x | x = x

• ~(~x) = x

• x ^ y = y ^ x
• x ^ (y ^ z) = (x ^ y) ^ z
• x ^ 0 = x
• x ^ y ^ y = x
• x ^ x = 0
• x ^ 0xFFFF = ~x

さらに、XORは3つの基本演算（AND、OR、NOT）を使用して構成できます。

• a ^ b = (a | b) & (~a | ~b)
• a ^ b = (a & ~b) | (~a & b)

• x | (x & y) = x
• x & (x | y) = x
• ~(x | y) = ~x & ~y
• ~(x & y) = ~x | ~y
• x | (y & z) = (x | y) & (x | z)
• x & (y | z) = (x & y) | (x & z)
• x & (y ^ z) = (x & y) ^ (x & z)
• x + y = (x ^ y) + ((x & y) << 1)
• x - y = ~(~x + y)

ブール代数では、通常の代数とは異なり、いくつかの演算に逆演算がないため、変数を解くのが難しくなる場合があります。逆演算のない演算を実行すると、元のデータ ビットの一部が失われ、この失われた情報を回復することはできません。

• 逆数を持つ
  • ない
  • 排他的論理和
  • 左に回転
  • 右に回転
• 逆はない
  • そして
  • または
  • 左にシフト
  • 右にシフト

このリストの一番上にある操作が最初に実行されます。より完全なリストについてはメインの記事を参照してください。

• ( )
• ~ -^[15]
• * / %
• + -^[16]
• << >>
• &
• ^
• |

• オンラインビット計算機はビットAND、OR、XORをサポートします
• XORcat、ビット単位のXORファイル/ストリーム用のツール
• ビットシフトを使用した除算
• 「Bitwise Operations Mod N」、Enrique Zeleny、Wolfram Demonstrations Project著。
• 「ビット演算の構成のプロット」、Enrique Zeleny、Wolfram デモンストレーション プロジェクト。