ビット演算(ビットえんざん、英: bitwise operation)とは、主にコンピュータで行われる演算のひとつで、データをビット列(つまり0か1が多数並んだもの)と見なして、各ビットの移動やビット単位での論理演算を行うもの[1]。 デジタルコンピュータの内部では、情報をビット列として表しており、CPUやMPUなどにはビット演算用の命令が多種用意されている[1]。特に機械語のプログラムでは多用される演算であり、高水準言語のソースコードでは直接記述されていない場合でも結局機械語に変換されて実行されるので、内部的に多用されている[1]。 ビット演算は大きく分けて次のように二種類ある[1]。 実装の観点からは、現在一般的なエレクトロニクス式デジタルコンピュータでは、加減算ではビットあたり数個程度の論理ゲートに加え多少複雑なキャリー伝搬の処理が、乗除算では多段に渡る処理が必要であるのに対し、ビット演算は1個か高々2個の論理ゲートで行えるため、多くの場合、最短サイクルしか必要としない。(つまりビット演算は、CPUの演算の中でも特に高速に行われる。)そのことから、高性能なプログラムを実現するための機械語コーディングではビット演算の使いこなしは重要なテクニックである[2]。また内部的には論理演算はALUで、(多桁の)シフトはバレルシフタで演算される。 各演算について説明し、その演算の基本を解説。ビット演算の種類を示す演算子をビット演算子(bitwise operator)という。おまけだが、各プログラミング言語での表記法も紹介する。 なお現状では肝心のアセンブリ言語での表記法(や文法)が説明されていないが、今後説明してゆく。とりあえずx86のアセンブリ言語でのビット演算の表記法については当ウィキペディアと姉妹サイトであるWikibookにまとめた記事があるのでそちらを参照のこと(x86, Logic ビット単位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を行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力のふたつのビットのどちらかでも 1 であれば、出力ビットは 1 となる。 0101OR 0011 = 0111 C/C++では、ビット単位OR演算子は "|" (縦棒)で表される。x = y 。z; この例では、"y OR z" の結果を x に格納する。これは、C/C++の論理「和」演算子 "||" (ふたつの縦棒)とは異なる。こちらは、オペランドを論理値として取り扱い、結果を "true" か "false" とする。 ビット単位ORは、ビット列がフラグ列として扱われるときによく使われる。つまり、各ビットが個別にブーリアン値を表している場合である。ある二進数値とひとつ以上の1を含むビット列とをビット単位ORを行うと、後者のビット列で 1 となっている位置が結果として出てくるビット列でも1となる。0010 このビット列は4つのフラグを表しているものとみなす。1番目、2番目、4番目は (0) にセットされていて、3番目が (1) にセットされている。1番目のフラグをセットするには、このビット列にビット単位ORを行えばよい。そのときのもう一方のビット列は1番目のビットだけを1にセットしておく。 0010OR 1000 = 1010 このテクニックはメモリが少ない環境向けのプログラムでよく使われる。ひとつのビットパターンで各種ステータスを一度に表現するのである。 また、MIPSアーキテクチャでは、命令セットを縮小するためにこれを使っている。MIPSではレジスタ間ロード(レジスタからレジスタへの値のコピー)命令がない。その代わりにゼロレジスタという常に内容がゼロで、何かを書き込んでも値が変わらないレジスタがある。そこで、レジスタ間ロードはビット単位OR命令を使って、ゼロレジスタとあるレジスタの ビット単位OR の結果を別のレジスタに格納することで実現される。 ビット単位XORは、ふたつの同じ長さのビットパターンを入力とし、同じ位置のビット毎に論理的XORを行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力するふたつのビットが違う値であれば、出力ビットは1となる。 0101XOR 0011 = 0110 C/C++では、ビット単位XOR演算子は "^" (サーカムフレックス)で表される。x = y ^ z; この例では、"y XOR z" の結果を x に格納する。 アセンブリ言語プログラマはレジスタの内容をゼロにしたいときに XOR 操作を行う。多くのアーキテクチャでは、ゼロという値をロードしてレジスタに格納するよりもXORを行う方がCPUクロックサイクルを消費せず、また命令長も短いためメモリを節約できる[4]。
概要
ビット単位の論理演算[1]
NOT, AND, OR, XORがある。
ビットの位置を入れ替える操作[1]
大きく分けるとシフト演算(一方向に単純に移動させる操作)とローテート演算(ビット列の先頭と末尾を繋いだように循環させる操作(「循環シフト」「環状シフト」「ビット回転」とも)がある[1]。
応用例
ビットマスク
IPアドレスの管理・制御
フラグ管理
画像処理[3]
並列アルゴリズムの実装(Bitapアルゴリズムなど)[注 1]
種類
論理演算
NOT
OR
XOR
Size:22 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef