Loading article…
コンピュータプログラミング において、ビット演算は、ビット列、ビット配列、または（ビット列とみなされる）二進数に対して、個々のビットレベルで操作を行う演算です。これは高速かつ単純な動作であり、高レベルの算術演算の基本となるもので、プロセッサによって直接サポートされています。ほとんどのアーキテクチャでは、高価値なビット演算はごく少数しか提供されておらず、それらは2つのオペランドからなる命令として表現され、結果が入力オペランドの1つを置き換える形をとります。
単純な低コストプロセッサでは、通常、ビット演算は除算よりもかなり速く、乗算よりも数倍速く、場合によっては加算よりもかなり速い。現代のプロセッサは、長い命令パイプラインやその他のアーキテクチャ設計上の選択により、加算と乗算をビット演算と同じくらい速く実行できるが、ビット演算はリソースの使用が少ないため、一般的に消費電力は少ない。[ 1 ]
以下の説明では、ビットの位置を示す数値はすべて右端（最下位）から左に向かって数えられます。例えば、2進数0001（10進数1）は、最初の位置（つまり一番右の位置）を除くすべての位置に0が配置されています。
ビットごとのNOT、またはビットごとの補数は、各ビットに対して論理否定を実行する単項演算であり、与えられたバイナリ値の1の補数を生成します。0のビットは1になり、1のビットは0になります。例：
0 111（10進数7）ではありません = 1,000 (10進数8)
10101011（10進数171）ではありません = 01010100 (10進数84)
結果は、値の2 の補数から 1 を引いた値に等しくなります。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) および 1 0 11 (10進数 11) = 0 0 10 (10進数2)
この性質のおかげで、最下位ビットの値を調べることで、2進数の偶数／奇数の状態を簡単に判定できます。上記の例を使用すると次のようになります。
011 0（10進数6） AND 000 1 (10進数 1) = 000 0 (10進数0)
6と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演算に対応する。
仮定すると非負整数の場合、ビット演算は次のように記述できます。
2 つのバイナリ変数には 16 通りの真理関数があります。これは、LUT2ルックアップ テーブル、別名ブール関数の順序 k=2 (2 つの入力) と呼ばれる真理テーブルを定義します。一部のベンダーは、特定のバイナリ 接続子を識別する 4 ビット フィールドを持つ命令に対して、接続子 [ 2 ] という用語を使用します。一部のベンダーは、 16 種類の異なるオペコードに対して、ブール演算[ 3 ]という用語を使用します。
2つのビットPとQのビットごとの等価演算を以下に示します。
三値相当のものは、次数 k=3 (3 つの入力) の LUT3ブール関数であり、256 の演算のテーブルとなり、コンピューティングではビット単位の三値論理命令と呼ばれます。
ビットシフトは、値を数値ではなくビット列として扱うため、ビット単位演算と呼ばれることもあります。これらの演算では、桁が左または右に移動（シフト）されます。コンピュータプロセッサのレジスタは幅が固定されているため、レジスタの一方の端からビットが「シフトアウト」され、もう一方の端から同じ数のビットが「シフトイン」されます。ビットシフト演算子の違いは、シフトインされたビットの値をどのように決定するかにあります。
レジスタの幅（多くの場合 32 または 64）が、アドレス指定可能な最小単位（多くの場合バイトと呼ばれる）のビット数（通常 8）よりも大きい場合、シフト操作によってバイトからビットへのアドレス指定方式が実現されます。これにより、「左」と「右」の方向は、位取り記法における数値の標準的な書き方から取られ、左シフトで数値の値が増加し、右シフトで数値の値が減少します。左側の桁を先に読み取ると、ビッグエンディアンの方向になります。レジスタの両端の境界効果を無視すると、算術シフト操作と論理シフト操作は同じように動作し、8 ビット位置のシフトは、次のように ビットパターンを 1 バイト位置分転送します。
算術シフト（スティッキーシフト）では、両端からシフトアウトされたビットは破棄されます。左算術シフトでは、ゼロが右側にシフトインされます。右算術シフトでは、符号ビット（2の補数表現における最上位ビット）が左側にシフトインされるため、オペランドの符号が保持されます。
この例では、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 nを掛けることと同等になります(ただし、値がオーバーフローしない場合)。一方、 2の補数の値に対してn だけ右に算術シフトすると、2 nで割った値の切り捨てと同等になります。バイナリ数を1 の補数として扱う場合、同じ右シフト操作は 2 nで割った値とゼロ方向への丸めになります。
論理シフト（ゼロフィルシフト）では、破棄されたビットの代わりにゼロが挿入されます。したがって、論理左シフトと算術左シフトは全く同じです。
しかし、論理右シフトは符号ビットをコピーする代わりに、最上位ビットに値0のビットを挿入するため、符号なし2進数に最適です。一方、算術右シフトは符号付き2の補数2進数に最適です。
シフトの別の形式は、循環シフト、ビット単位の回転、またはビット回転です。
この操作は「ローテーション・ノー・キャリー」とも呼ばれ、レジスタの左端と右端が結合されたかのようにビットが「回転」されます。左シフト時に右にシフトされる値は、左にシフトアウトされた値と同じであり、右シフト操作の場合はその逆になります。これは、既存のすべてのビットを保持する必要がある場合に便利で、デジタル暗号化で頻繁に使用されます。
キャリーによる回転は回転操作の変形であり、シフトインされるビット（両端のいずれか）はキャリーフラグの古い値であり、シフトアウトされるビット（もう一方の端）はキャリーフラグの新しい値になります。
キャリーフラグを事前に設定することで、単一のキャリー経由回転命令x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEは、1ビットの論理シフトまたは算術シフトをシミュレートできます。たとえば、キャリーフラグが0の場合は論理右シフト、キャリーフラグが符号ビットのコピーの場合はx RIGHT-ROTATE-THROUGH-CARRY-BY-ONE算術右シフトとなります。このため、低価格帯のPICなどの一部のマイクロコントローラは、回転命令とキャリー経由回転命令のみを備えており、算術シフト命令や論理シフト命令は実装していません。
キャリーを介した回転は、プロセッサのネイティブワードサイズよりも大きな数値をシフトする場合に特に役立ちます。なぜなら、大きな数値が2つのレジスタに格納されている場合、最初のレジスタの一方の端からシフトアウトされたビットは、2番目のレジスタのもう一方の端からシフトインされる必要があるからです。キャリーを介した回転を使用すると、そのビットは最初のシフト中にキャリーフラグに「保存」され、2回目のシフト時に特別な準備なしにシフトインできるようになります。
C および C++ 言語では、論理シフト演算子は左シフトの場合は " 、右シフトの場合は " です。シフトする桁数は、演算子の 2 番目の引数として指定します。たとえば、<<>>
![{\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)\\&=\left(2^{\lfloor \log _{2}x\rfloor +1}-1\right)-x\\[10pt]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)\\[10pt]x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}x\rfloor }2^{n}{\Bigg (}\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\\&\qquad \qquad -\left(\left\lfloor {\frac {x}{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}}} {y}{2^{n}}}\right\rfloor {\bmod {2}}\right){\Bigg )}\\[10pt]x\operatorname {XOR} y&=\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7647cbf02ef730027a0db2fd726c023ff93eb028)
x = y << 2 ;これは、2ビット左xシフトした結果を代入するもので、4倍に相当します。y
シフトは実装定義の動作または未定義の動作を引き起こす可能性があるため、使用時には注意が必要です。ワードのサイズ以上のビット数だけシフトした場合、C および C++ では未定義の動作になります。[ 4 ] [ 5 ]負の値を右シフトすると実装定義の動作となり、適切なコーディングの慣習では推奨されません。[ 6 ]符号付き値を左シフトした場合、結果が結果型で表現できない場合は未定義となります。[ 4 ]
C# では、最初のオペランドが int または long の場合、右シフトは算術シフトになります。最初のオペランドが uint または ulong 型の場合、右シフトは論理シフトになります。[ 7 ]
C言語ファミリーには回転演算子がありません（C++20ではとが提供されていますがstd::rotl）が、シフト演算子から合成することができます。セキュリティ要件のあるソフトウェアでは、未定義動作やタイミング攻撃をstd::rotr避けるために、ステートメントが正しく構成されていることを確認する必要があります。 [ 8 ]例えば、32ビット符号なし値を位置だけ左回転させる単純な実装は、単純に次のようになります。xn
uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( 32 - n ));しかし、ビットシフトすると、0右辺の式で未定義の動作が発生します。(x >> (32 - n))なぜなら、32 - 0はであり、は0～31の範囲外だからです。2回目の試行では、3232
uint32_t x = ..., n = ...; uint32_t y = n ? ( x << n ) | ( x >> ( 32 - n )) : x ;シフト量がテストされ、未定義の動作を引き起こさないことが保証されます。ただし、この分岐は追加のコードパスを追加し、タイミング解析や攻撃の機会を生み出しますが、これは多くの場合、高信頼性ソフトウェアでは許容されません。[ 8 ]さらに、このコードは複数のマシン命令にコンパイルされますが、これは多くの場合、プロセッサのネイティブ命令よりも効率が悪くなります。
GCCおよびClangでの未定義の動作と分岐を回避するために、以下が推奨されます。このパターンは多くのコンパイラで認識され、コンパイラは単一の回転命令を出力します。[ 9 ] [ 10 ] [ 11 ]
uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( x >> ( - n & 31 ));また、Microsoft Visual C++の_rotl8、_rotl16、_rotr8、_rotr16のように、循環シフトを実装するコンパイラ固有の組み込み関数もあります。Clang は、Microsoft との互換性のためにいくつかの回転組み込み関数を提供していますが、上記の問題があります。[ 11 ] GCC 15 はと組み込み関数を導入しましたが、それらを適切に最適化できませんでした。Intel も x86組み込み関数を提供しています。__builtin_stdc_rotate_left__builtin_stdc_rotate_right
Java では、すべての整数型は符号付きなので、「」演算子と「」演算子は算術シフトを実行します。Java では論理右シフトを実行するために「 」演算子が追加されていますが、符号付き整数では論理左シフトと算術左シフトの操作が同じであるため、Java には「 」演算子はありません。<<>>>>><<<
Javaシフト演算子の詳細については、[ 12 ]を参照してください。
<<(左シフト)、>>(符号付き右シフト)、および(符号なし右シフト) はシフト演算子>>>と呼ばれます。aByte >>> 2と同等です。((int)aByte)>>>2n >>> sビット位置です。byte暗黙的に に変換されますint。バイト値が負の場合、最上位ビットは 1 となり、1 が int の余剰バイトを埋めるために使用されます。したがって、 はになります。byteb1=-5;inti=b1|0x0200;i == -5JavaScriptはビット演算を使用して、2つ以上のユニットのそれぞれを1または0に評価します。 [ 14 ]
Pascal およびそのすべての方言 ( Object PascalやStandard Pascalなど) では、論理左シフト演算子と論理右シフト演算子はそれぞれ " shl" と " shr" です。符号付き整数の場合でも、shrは論理シフトのように動作し、符号ビットはコピーされません。シフトする桁数は、2 番目の引数で指定します。たとえば、次のコードは、y を2 ビット左にシフトした結果をxに代入します。
x := y shl 2 ;ビット演算は、デバイスドライバ、低レベルグラフィックス、通信プロトコルパケットの組み立て、およびデコードといった低レベルプログラミングにおいて特に必要となる。
機械には算術演算や論理演算を実行するための効率的な組み込み命令が備わっていることが多いが、これらの演算はすべて、ビット演算子とゼロテストをさまざまな方法で組み合わせることで実行できる。[ 15 ] 例えば、以下は古代エジプトの乗算の擬似コード実装で、任意の2つの整数と（より大きい）をビットシフトと加算のみを使用して乗算する方法を示している。abab
c ← 0 while b ≠ 0 if ( b and 1 ) ≠ 0 c ← c + a left shift a by 1 right shift b by 1 return cもう一つの例は、加算の擬似コードによる実装で、ビット演算子とゼロテストを使用してa2つの整数の合計を計算する方法を示しています。b
a ≠ 0の間、c ← bかつa b ← b aを xor し、cを 1左シフトし、a ← cを実行し、 bを返す。コンパイラを作成する際など、ビット演算で構成される複雑な式を簡略化することが有用な場合があります。コンパイラの目的は、高水準プログラミング言語を可能な限り効率的な機械語に変換することです。複雑なビット演算式を簡略化するために、ブール代数が用いられます。
x & y = y & xx & (y & z) = (x & y) & zx & 0xFFFF = x[ 16 ]x & 0 = 0x & x = xx | y = y | xx | (y | z) = (x | y) | zx | 0 = xx | 0xFFFF = 0xFFFFx | x = x~(~x) = xx ^ y = y ^ xx ^ (y ^ z) = (x ^ y) ^ zx ^ 0 = xx ^ y ^ y = xx ^ x = 0x ^ 0xFFFF = ~xさらに、XORは3つの基本演算（AND、OR、NOT）を組み合わせて構成することもできます。
a ^ b = (a | b) & (~a | ~b)a ^ b = (a & ~b) | (~a & b)x | (x & y) = xx & (x | y) = x~(x | y) = ~x & ~y~(x & y) = ~x | ~yx | (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)ブール代数では、通常の代数とは異なり、逆演算を持たない演算がいくつか存在するため、変数を求めるのは難しい場合があります。逆演算を持たない演算は、実行時に元のデータビットの一部を失い、失われた情報を復元することはできません。
このリストの上位にある操作が最初に実行されます。より詳細なリストについては、メイン記事を参照してください。