|
ビット演算ビット演算（ビットえんざん、英: bitwise operation）とは、主にコンピュータで行われる演算のひとつで、データをビット列（つまり0か1が多数並んだもの）と見なして、各ビットの移動やビット単位での論理演算を行うもの[1]。 概要デジタルコンピュータの内部では、情報をビット列として表しており、CPUやMPUなどにはビット演算用の命令が多種用意されている[1]。特に機械語のプログラムでは多用される演算であり、高水準言語のソースコードでは直接記述されていない場合でも結局機械語に変換されて実行されるので、内部的に多用されている[1]。 ビット演算は大きく分けて次のように二種類ある[1]。
実装の観点からは、現在一般的なエレクトロニクス式デジタルコンピュータでは、加減算ではビットあたり数個程度の論理ゲートに加え多少複雑なキャリー伝搬の処理が、乗除算では多段に渡る処理が必要であるのに対し、ビット演算は1個か高々2個の論理ゲートで行えるため、多くの場合、最短サイクルしか必要としない。（つまりビット演算は、CPUの演算の中でも特に高速に行われる。）そのことから、高性能なプログラムを実現するための機械語コーディングではビット演算の使いこなしは重要なテクニックである[3]。また内部的には論理演算はALUで、（多桁の）シフトはバレルシフタで演算される。
種類各演算について説明し、その演算の基本を解説。 ビット演算の種類を示す演算子をビット演算子（bitwise operator）という。おまけだが、各プログラミング言語での表記法も紹介する。 なお現状では肝心のアセンブリ言語での表記法（や文法）が説明されていないが、今後説明してゆく。とりあえずx86のアセンブリ言語でのビット演算の表記法については当ウィキペディアと姉妹サイトであるWikibookにまとめた記事があるのでそちらを参照のこと(x86, Logic、 x86, Shift and Rotate)。 論理演算NOTビット単位NOTあるいは補数とは論理否定を各ビットに対して行う単項演算。0 は 1 になり、1 は 0 になる。各ビットを反転させるのでビット反転ともいう。 NOT 0111 = 1000 C言語やC++では、NOT演算子は " x = ~y; この例では、x に "NOT y" の結果を格納する。これは、Cおよび C++の論理「否定」演算子 " x = !y; この例では、x に y が "false" であれば "true" を表すブーリアン値を格納し、y が "true" であれば "false" を格納する。CやC++では、数値はゼロでないとき "true" を示すとされる。論理「否定」はビットレベルの演算ではないので、一般的にはビット演算とは考えられない。 ビット単位NOTは二進数値の1の補数を作るのに使える。そして2の補数を作るときの途中の段階にも使われる。 ORビット単位ORは、ふたつの同じ長さのビットパターンを入力とし、同じ位置のビット毎に論理的ORを行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力のふたつのビットのどちらかでも 1 であれば、出力ビットは 1 となる。 0101 OR 0011 = 0111 C/C++では、ビット単位OR演算子は " x = y | z; この例では、"y OR z" の結果を x に格納する。これは、C/C++の論理「和」演算子 " ビット単位ORは、ビット列がフラグ列として扱われるときによく使われる。つまり、各ビットが個別にブーリアン値を表している場合である。ある二進数値とひとつ以上の1を含むビット列とをビット単位ORを行うと、後者のビット列で 1 となっている位置が結果として出てくるビット列でも1となる。 0010 このビット列は4つのフラグを表しているものとみなす。1番目、2番目、4番目は (0) にセットされていて、3番目が (1) にセットされている。1番目のフラグをセットするには、このビット列にビット単位ORを行えばよい。そのときのもう一方のビット列は1番目のビットだけを1にセットしておく。 0010 OR 1000 = 1010 このテクニックはメモリが少ない環境向けのプログラムでよく使われる。ひとつのビットパターンで各種ステータスを一度に表現するのである。 また、MIPSアーキテクチャでは、命令セットを縮小するためにこれを使っている。MIPSではレジスタ間ロード(レジスタからレジスタへの値のコピー)命令がない。その代わりにゼロレジスタという常に内容がゼロで、何かを書き込んでも値が変わらないレジスタがある。そこで、レジスタ間ロードはビット単位OR命令を使って、ゼロレジスタとあるレジスタの ビット単位OR の結果を別のレジスタに格納することで実現される。 XORビット単位XORは、ふたつの同じ長さのビットパターンを入力とし、同じ位置のビット毎に論理的XORを行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力するふたつのビットが違う値であれば、出力ビットは1となる。 0101 XOR 0011 = 0110 C/C++では、ビット単位XOR演算子は " x = y ^ z; この例では、"y XOR z" の結果を x に格納する。 アセンブリ言語プログラマはレジスタの内容をゼロにしたいときに XOR 操作を行う。多くのアーキテクチャでは、ゼロという値をロードしてレジスタに格納するよりもXORを行う方がCPUクロックサイクルを消費せず、また命令長も短いためメモリを節約できる[5]。同じ値をビット単位XORのふたつの入力として使うと、出力は常にゼロになる。つまり、同じレジスタを指定したXOR命令を実行して同じレジスタに戻すことでその内容をゼロにすることができる。もちろん、MIPSアーキテクチャの場合は入力としてゼロレジスタを使えば、ORでも XORでもANDでもADDでも結果をゼロにすることができる。 ビット単位XORはフラグの値を変更するときにも使われる。 0010 このビットパターンで1番目のビットと3番目のビットを同時に変更したい場合、もうひとつのビットパターンで、その変えたい位置に1を置いておく。 0010 XOR 1010 = 1000 このテクニックはビットパターンをブーリアン変数の並びとして扱うときに使われるだろう。
ANDビット単位ANDは、ふたつの同じ長さのビットパターンを入力とし、同じ位置のビット毎に論理的ANDを行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力するふたつのビットがどちらも1であれば、出力ビットは 1 となる。 0101 AND 0011 = 0001 C/C++では、ビット単位AND演算子は " x = y & z; この例では、"y AND z" の結果を x に格納する。これは、C/C++の論理「積」演算子 " ビット単位ANDはビットマスク操作として使われることもある。これは、ビット列の一部を取り出すのに使われたり、ある特定のビットが1か0かを調べるのにも使われる。 例
11001011 この例で、末尾4ビットぶんのデータを取り出すには、取り出したいビット位置だけを 1 にしたビットパターンを入力する。 11001011 AND 1111 = 1011
0101 この例で、二番目のビットが 1 かどうかを調べるには、ビット単位ANDに対して、その調べたいビット位置だけを1にしたビットパターンを入力する。 0101 AND 0010 = 0000 この結果はゼロなので、二番目のビットは0であったことがわかる。このようなビット単位ANDの使い方はビットマスクと呼ばれる。このとき、関心のないビット位置は0にする。 ビットシフトビットシフトも、通常ビット演算の一種として扱われる。[注釈 1] ビットシフトは大きく分けるとシフト演算（一方向に単純に移動させる操作）とローテート演算（ビット列の先頭と末尾を繋いだように循環させる操作（「循環シフト」「環状シフト」「ビット回転」とも）とに分けられる[1]。 全ビットを一律に移動する操作を「論理シフト」（英: logical shift）という。一方、右シフトの際に最上位ビットだけは動かさずに保存するシフト操作を「算術シフト」（英: arithmetic shift）といい、これは最上位ビットを符号ビットとする「符号付き整数」を処理するのに適している[1]。 コンピュータのプロセッサ内のレジスタのビット数（桁数）は有限であるので、これに対するシフト演算（一方向に単純に移動させる操作）はいくつかのビットがレジスタからはみ出す。外から入ってくるビットとはみ出すビットをどう扱うかにより、いくつもの種類がある。 算術シフト算術シフトでは、右シフトにおいて、最上位ビット（2の補数表現であれば符号ビット）は保存される。左シフトは、（一部例外を除き[6]）後述する論理シフトと同じもので、空くビット位置にはゼロが入る。このシフトではあふれたビットは単に消える（プロセッサの実装によってはフラグに入るものもある）。下記の例は 4ビットレジスタの場合である。 0111 LEFT-SHIFT = 1110 1011 RIGHT-SHIFT = 1101 前者の例は、左端の0はあふれて消え、あらたな0が右端に入れられている。後者の例は、右端の1はあふれて消え、符号ビット1が左端にコピーされている。あふれたビットは、多くの場合キャリーフラグにセットされる。マルチプルシフトは、シングルシフトをくりかえしたものと同じ結果になる。 0111 LEFT-SHIFT-BY-TWO = 1100 C/C++では、左シフトと右シフトは " x = y << 2; この例では、y を2桁左に算術シフトした結果を x に格納する。 1ビットの左算術シフトは2倍するのと同じである。1ビットの右算術シフトは、値が非負であれば2で割ってあまりを捨てるのと同じである。 負の値を右に算術シフトした場合は、シフトしてあふれたビットが1なら（複数シフトの場合は、あふれたビットの中に1がある場合には）、結果に1を足せば、2または2のべきで割ってあまりを捨てるのと同じになる。 論理シフト論理シフトでは、右シフトのときも空いたビットをゼロにする。他は算術シフトと同様である。したがって、論理シフトは符号無しの二進数を扱うのに適していて、算術シフトは2の補数表現の符号付き二進数を扱うのに適している。 (キャリーなし)ローテートもうひとつのシフトとして循環シフトすなわちビット・ローテーションがある。これはビット列の左端と右端がつながっているように扱ってシフトするものである。シフト方向の端をあふれた桁は逆の端に置かれる。これは、存在するビットを残しておく必要があるとき、ビットの位置を変えるのに使われたりする。 キャリーつきローテート
こちらはローテート操作の際に、（キャリー）フラグを挟んで、ビット列の左端と右端がつながっているように扱う。フラグに最上位ビットのコピーを入れておけば算術シフトを、0を入れておけば論理シフトをシミュレートできることから、PICのようなマイクロコントローラではローテートとキャリー付きローテートだけを用意して、算術シフトや論理シフト命令は用意しないものもある。キャリー付きローテートは特にプロセッサのレジスタのビット幅より大きな数値のシフトを実現する場合に便利である。 その他使用例マシンは算術演算や論理演算をするのに十分な命令を持っているが、実際全ての演算はビット演算の組み合わせと何らかのゼロ判定機能があれば実現できる。例えば、下記の例はふたつの任意の整数 a と b の乗算をビットシフトと加算で実現する擬似コードである。 c := 0
while b ≠ 0
if b and 1 ≠ 0
c := c + a
shift a left by one
shift b right by one
return c
注意事項ビットシフトに対して右オペランド（シフト量）の値が負である場合、あるいは左オペランドの型のビット数を超える場合の規定は言語によって異なる（あるいは言語によって規定されておらず、処理系定義や未定義や未規定であったりする）。 Java[7]、.NET言語 (C#、VB.NETなど)、JavaScriptなどでは「左オペランドの型のビット数-1」のビット単位ANDのマスクを右オペランドにかける。これは最低でも1ビットは値を残すための配慮である。以下にC#の例を示す。 class BitShift
{
static void Main()
{
int i = 1; // 32 bits
long l = 1; // 64 bits
// output: 0x2 (33 & (32-1) = 1 なので 1 ビット左シフト)
System.Console.WriteLine("0x{0:x}", i << 33);
// output: 0x200000000 (33 & (64-1) = 33 なので 33 ビット左シフト)
System.Console.WriteLine("0x{0:x}", l << 33);
}
}
C/C++ の ISO の仕様では、このような場合の結果は未定義となっている。GCC や Visual C++ の実装においては、Warning が出るが、上記と同じ結果を返す。 脚注
関連項目 |
