ビット演算

ビット演算（ビットえんざん）とは、ひとつあるいはふたつのビットパターンまたは二進数を個々のビットの列として操作することである。

CPU設計の観点からは、ビット演算は簡単な論理回路で実現できるが、四則演算、特に乗除算は複雑な論理回路を必要とするため、多くのコンピュータでは、ビット演算は加減算より若干速く、乗除算よりずっと高速である。

ビット演算はビットマスクと呼ばれる手法を用いたフラグ管理などに用いられるほか、その並列性からオートマトン実装に用いられる場合もある（→Bitapアルゴリズム）。

ビット演算子

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++の論理「和」演算子 "||" （ふたつの縦棒）とは異なる。こちらは、引数を論理値として取り扱い、結果を "true" か "false" とする。

ビット単位ORは、ビット列がフラグ列として扱われるときによく使われる。つまり、各ビットが個別にブーリアン値を表している場合である。ある二進数値とひとつ以上の1を含むビット列とをビット単位ORを行うと、後者のビット列で 1 となっている位置が結果として出てくるビット列でも1となる。

このビット列は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クロックサイクルを消費せず、また命令長も短いためメモリを節約できる。同じ値をビット単位XORのふたつの入力として使うと、出力は常にゼロになる。つまり、同じレジスタを指定したXOR命令を実行して同じレジスタに戻すことでその内容をゼロにすることができる。もちろん、MIPSアーキテクチャの場合は入力としてゼロレジスタを使えば、ORでも XORでもANDでもADDでも結果をゼロにすることができる。

ビット単位XORはフラグの値を変更するときにも使われる。

このビットパターンで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++の論理「積」演算子 "&&" （ふたつのアンパサンド）とは異なる。こちらは、引数をブーリアン値として取り扱い、結果を "true" か "false" とする。

ビット単位ANDはビットマスク操作として使われることもある。これは、ビット列の一部を取り出すのに使われたり、ある特定のビットが1か0かを調べるのにも使われる。

この例で、三番目のビットが 1 かどうかを調べるには、ビット単位ANDに対して、その調べたいビット位置だけを1にしたビットパターンを入力する。

    0101
AND 0010
  = 0000

この結果はゼロなので、三番目のビットは0であったことがわかる。このようなビット単位ANDの使い方はビットマスクと呼ばれる。このとき、関心のないビット位置は0にする。

シフト

シフトはときにビット演算の一種とみなされる。というのは、それがビット列に対する操作だからである。それとは逆にシフトは数値全体に対するものでビット毎に操作するものではないという考え方もある。この操作では各桁を右か左に移動させる。コンピュータのプロセッサ内のレジスタは固定のビット長を持っていて、数値を格納する。これに対するシフトはいくつかのビットがレジスタからはみ出すことを意味する。シフトにいろいろな種類があるのは、外から入ってくるビットと、はみ出すビットをどう扱うかが違うためである。

算術シフト

算術シフトでは、右シフトにおいて、最上位ビット（2の補数表現であれば符号ビット）は保存される。左シフトでは、空くビット位置には、ゼロが入る。このシフトではあふれたビットは単に消える（プロセッサの実装によってはフラグに入るものもある）。下記の例は 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の補数表現の符号付き二進数を扱うのに適している。

(キャリーなし)ローテート

もうひとつのシフトとして環状シフトまたはビット・ローテーションがある。これはビット列の左端と右端がつながっているように扱ってシフトするものである。シフト方向の端をあふれた桁は逆の端に置かれる。これは、存在するビットを残しておく必要があるとき、ビットの位置を変えるのに使われたりする。

キャリーつきローテート

ファイル:Rotate right through carry.svg

キャリーつき右ローテート

ファイル:Rotate left through carry.svg

キャリーつき左ローテート

こちらはローテート操作の際に、（キャリー）フラグを挟んで、ビット列の左端と右端がつながっているように扱う。フラグに最上位ビットのコピーを入れておけば算術シフトを、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

注意事項

ビットシフトに対して第2引数の値が負である場合、あるいは第1引数の型のビット数を超える場合の規定は言語によって異なる。 C#, ECMAScript, VisualBasic等では第1引数の型のビット数-1のビット単位ANDのマスクを第2引数にかける。これは最低でも1ビットは値を残すための配慮である。以下に例を示す。

class BitShift
{
    static void Main()
    {
        int  i = 1;  // 32 bits
        long lg = 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}", lg << 33);
    }
}

一方、C, C++ の標準では、このような場合の結果は未定義となっている。

Javaでは右シフトに>>と>>>の2種類があり、算術シフトと論理シフトが分かれている。C, C++ の標準では、負の値を右シフトした場合の結果は処理系定義である。

ビット演算

目次