ビット操作

ビット操作とは、ビットまたはワードより短い他のデータ部分をアルゴリズム的に操作する行為です。ビット操作を必要とするコンピュータ プログラミングタスクには、低レベルのデバイス制御、エラー検出および修正アルゴリズム、データ圧縮、暗号化アルゴリズム、最適化などがあります。その他のほとんどのタスクでは、現代のプログラミング言語により、プログラマーは抽象化を表すビットではなく、 抽象化を直接操作できます。

ビット操作を行うソース コードでは、ビット単位の演算(AND、OR、XOR、NOT) や、ブール演算子に類似したその他の演算が使用されます。また、ビット シフトや、1 と 0 をカウントする、上位 1 または 0 と下位 1 または 0 を検索する、ビットを設定、リセット、テストする、フィールドを抽出および挿入する、フィールドをマスクおよびゼロ化する、指定されたビット位置またはフィールドとの間でビットを収集および分散するなどの演算もあります。整数算術演算子は、他の演算子と組み合わせてビット演算を行うこともできます。

ビット操作は、場合によっては、データ構造をループする必要性をなくすか減らすことができ、ビット操作が並列に処理されるため、速度が何倍にも向上します。

ビット操作、ビットいじり、ビット叩き、ビット体操は、多くの場合、ビット操作と同じ意味で使用されますが、ビット操作の巧妙な、または自明でない方法や使用法、あるいは退屈で困難な低レベルのデバイス制御データ操作タスク のみを指す場合もあります。

ビット操作という用語は、コンピューター オペレーターがコンピューター コントロールを微調整したり操作したりして調整を行った初期のコンピューター ハードウェアに由来します。コンピューター プログラミング言語が進化するにつれて、プログラマーはこの用語を、ビット レベルの計算を伴うデータの処理を意味するものとして採用しました。

ビット演算は、1 つ以上のビット パターンまたは2 進数値を個々のビットのレベルで操作します。これは、中央処理装置(CPU)によって直接サポートされる高速で基本的なアクションであり、比較や計算のために値を操作するために使用されます。

ほとんどのプロセッサでは、ビット演算の大部分は 1 サイクルで実行され、除算、乗算、分岐よりも大幅に高速です。最近のプロセッサは、命令パイプラインが長く、その他のアーキテクチャ設計の選択により、一部の算術演算や論理演算をビット演算と同じ速度で実行するのが一般的ですが、ビット演算ではリソースの使用が減るため、消費電力が少なくなるのが一般的です。

数が 2 の累乗であるかどうかを判断するには、概念的には、数が 2 で均等に割り切れなくなるまで整数を 2 で繰り返し割ります。残っている因数が 1 だけであれば、元の数は 2 の累乗です。ビット演算子と論理演算子を使用すると、true (1) または false (0) を返す簡単な式があります。

bool isPowerOfTwo = ( x != 0 ) && (( x & ( x - 1 )) == 0 );             

後半では、2 の累乗の 2 進表現では 1 ビットのみが設定されるという事実を利用しています。

x == 0...0 1 0...0
x-1 == 0...001...1
x & (x-1) == 0...000...0

数値が 0 でも 2 の累乗でもない場合は、複数の場所に '1' が含まれます。

x == 0... 1 ...0 1 0...0
x-1 == 0... 1 ...001...1
x & (x-1) == 0... 1 ...000...0

インラインアセンブリ言語コードを使用する場合、オペランド内の 1 または 0 の数をカウントする命令 ( popcnt ) が使用できる可能性があります。1 ビットだけを持つオペランドは 2 の累乗です。ただし、このような命令は、上記のビット単位の方法よりもレイテンシが大きくなる可能性があります。

プロセッサは通常、有用なビット演算子のサブセットのみを提供します。プログラミング言語はほとんどのビット演算を直接サポートしていないため、それらをコード化するには慣用句を使用する必要があります。たとえば、'C' プログラミング言語はビット単位の AND(&)、OR(|)、XOR(^)、NOT(~) のみを提供します。Fortran は AND(.and.)、OR (.or.)、XOR (.neqv.)、EQV(.eqv.) を提供します。Algol は構文ビットフィールドの抽出と挿入を提供します。言語がハードウェア命令に直接マップされないビット演算を提供する場合、コンパイラは使用可能な演算子から演算を合成する必要があります。

特に便利なビット操作は、マシン ワードの高位セット ビットを見つけるために使用されるcount leading zerosですが、さまざまなアーキテクチャで異なる名前が付けられている場合があります。 ^[1] 簡単なプログラミング言語イディオムがないため、コンパイラ組み込み関数またはシステム ライブラリ ルーチンで提供する必要があります。 この演算子がないと、算術演算の非対称キャリー伝播のため、ワードの高位ビットに関する操作を実行するのは非常にコストがかかります ( Find first set#CLZを参照)。 幸いなことに、ほとんどの CPU アーキテクチャは 1980 年代半ばからこれを提供しています。 付随するcount ones操作(POPCOUNT とも呼ばれます) も、マシン ワード内のセット ビットの数をカウントし、通常はハードウェア演算子として提供されます。 ビット セット、リセット、テスト、トグルなどのより単純なビット操作は、多くの場合ハードウェア演算子として提供されますが、提供されていない場合は簡単にシミュレートできます。たとえば、(SET R0, 1; LSHFT R0, i; OR x, R0) は、オペランド x のビット i を設定します。

プログラミング言語で慣用句としてコード化され、コンパイラによって合成される必要がある、より有用で複雑なビット操作には、次のものがあります。

• 指定されたビット位置から上にクリアする（ワードの下位部分は残す）
• 指定されたビット位置から下をクリアする（ワードの上位部分は残す）
• 下位ビットからマスクする（下位ワードをクリア）
• 上位ビットからマスク（下位ワードをクリア）
• ビットフィールド抽出
• ビットフィールド挿入
• ビットフィールドのスキャッター/ギャザー操作は、マシン ワード上のビットフィールドの連続部分を分散したり、ワード内の異なるビットフィールドをビットフィールドの連続部分に集めたりします (最新の Intel PEXT/PDEP 演算子を参照)。暗号化とビデオ エンコードで使用されます。
• 行列反転

いくつかの算術演算は、より単純な演算とビット演算に簡略化できます。

• 定数による乗算をシフト加算のシーケンスに減らす

たとえば、9 を掛けると、オペランドがコピーされ、3 シフトされ (8 を掛け)、元のオペランドに追加されます。

• 定数による除算をシフト減算のシーケンスに減らす

マスクは、特にビット フィールド内でビット単位の演算に使用されるデータです。

マスクを使用すると、バイト、ニブル、ワードなどの複数のビットを、単一のビット演算でオン、オフ、またはオンからオフへの反転（またはその逆）に設定できます。 マスクをより包括的に応用し、条件付きで演算に適用することを、述語と呼びます。

• ビット配列
• ビットバンディング
• ビットバンギング
• ビットフィールド
• ビット操作命令セット— x86命令セットのビット操作拡張機能。
• BIT述語
• ビット仕様（曖昧さ回避）
• ビットツイドラー（曖昧さ回避）
• ニブル— 4ビット、または半バイトで構成されるデータの単位
• ベクトルプロセッサでビット「マスク」が使用される予測（コンピュータアーキテクチャ）
• シングルイベントの番狂わせ

• ウォーレン、ヘンリー S. (2013)。Hacker 's Delight (第 2 版)。Addison–Wesley Professional。p. 512。ISBN 978-0321842688。
• Knuth, Donald E. (2009)。『コンピュータプログラミングの技法』第 4 巻、第 1 巻: ビット単位のトリックとテクニック、二分決定図(第 1 版)。Addison–Wesley Professional。p. 272。ISBN 978-0321580504。(Fascicle 1a の草稿は 2019-10-16 にアーカイブされ、Wayback Machineでダウンロード可能です)

• アンダーソン、ショーン・エロン編 (2009-11-26) [1997]。「Bit Twiddling Hacks」。スタンフォード大学。2020-06-01にオリジナルからアーカイブ。2020-06-01に取得。
• 完全な説明とソースコード付きのビット操作トリック
• Intel イントリンシクス ガイド
• xchg rax、rax: x86_64 の謎とハック
• ケンタッキー大学の集約マジックアルゴリズム