ビット演算のソースを表示

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

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

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

== ビット演算子 ==
=== NOT ===
'''ビット単位NOT'''あるいは'''補数'''とは論理[[否定]]を各ビットに対して行う単項演算。0 は 1 になり、1 は 0 になる。

 NOT 0111
   = 1000

[[C言語]]や[[C++言語]]では、NOT演算子は "<code>~</code>" （チルダ）である。

 x = ~y;

この例では、''x'' に "NOT ''y''" の結果を格納する。これは、Cおよび C++の論理「否定」演算子 "<code>!</code>" （エクスクラメーションマーク）とは異なる。こちらは与えられた数値全体をひとつの[[ブーリアン]]として扱う。

 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演算子は "<code>|</code>" （縦棒）で表される。

 x = y | z;

この例では、"''y'' OR ''z''" の結果を ''x'' に格納する。これは、C/[[C++]]の論理「和」演算子 "<code>||</code>" （ふたつの[[バーティカルバー|縦棒]]）とは異なる。こちらは、引数を論理値として取り扱い、結果を "true" か "false" とする。

ビット単位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演算子は "<code>^</code>" （[[サーカムフレックス]]）で表される。

 x = y ^ z;

この例では、"''y'' XOR ''z''" の結果を ''x'' に格納する。

[[アセンブリ言語]]プログラマはレジスタの内容をゼロにしたいときに XOR 操作を行う。多くのアーキテクチャでは、ゼロという値をロードしてレジスタに格納するよりもXORを行う方が[[CPU]]クロックサイクルを消費せず、また命令長も短いため[[メモリ]]を節約できる。同じ値をビット単位XORのふたつの入力として使うと、出力は常にゼロになる。つまり、同じレジスタを指定したXOR命令を実行して同じレジスタに戻すことでその内容をゼロにすることができる。もちろん、MIPSアーキテクチャの場合は入力としてゼロレジスタを使えば、ORでも XORでもANDでもADDでも結果をゼロにすることができる。

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

 0010

このビットパターンで1番目のビットと3番目のビットを同時に変更したい場合、もうひとつのビットパターンで、その変えたい位置に1を置いておく。

     0010
 XOR 1010
   = 1000

このテクニックはビットパターンをブーリアン変数の並びとして扱うときに使われるだろう。

==== 関連項目 ====
* [[XOR交換アルゴリズム]]、[[XOR連結リスト]]

=== AND ===
'''ビット単位AND'''は、ふたつの同じ長さのビットパターンを入力とし、同じ位置のビット毎に論理的[[論理積|AND]]を行って同じ長さのビットパターンを出力する操作である。各ビット位置で、入力するふたつのビットがどちらも1であれば、出力ビットは 1 となる。

     0101
 AND 0011
   = 0001

C/C++では、ビット単位AND演算子は "<code>&</code>" （[[アンパサンド]]）で表される。

 x = y & z;

この例では、"''y'' AND ''z''" の結果を ''x'' に格納する。これは、C/C++の論理「積」演算子 "<code>&&</code>" （ふたつのアンパサンド）とは異なる。こちらは、引数をブーリアン値として取り扱い、結果を "true" か "false" とする。

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

 0101

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

     0101
 AND 0010
   = 0000

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

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

=== 算術シフト ===
<!--
[[Image:ShiftLeft.JPG|thumb|Left shift]]
[[Image:ArithmaticShiftRight.JPG|thumb|Right arithmetic shift]]
-->
'''算術シフト'''では、右シフトにおいて、最上位ビット（[[2の補数]]表現であれば符号ビット）は保存される。左シフトでは、空くビット位置には、ゼロが入る。このシフトではあふれたビットは単に消える（プロセッサの実装によってはフラグに入るものもある）。下記の例は 4ビットレジスタの場合である。

   0111 LEFT-SHIFT
 = 1110

   1011 RIGHT-SHIFT
 = 1101

前者の例は、左端の0はあふれて消え、あらたな0が右端に入れられている。後者の例は、右端の1はあふれて消え、符号ビット1が左端にコピーされている。あふれたビットは、多くの場合キャリーフラグにセットされる。マルチプルシフトは、シングルシフトをくりかえしたものと同じ結果になる。

   0111 LEFT-SHIFT-BY-TWO
 = 1100

C/C++では（他の言語でも）、左シフトと右シフトは "<code>&lt;&lt;</code>" と "<code>&gt;&gt;</code>" で表される。シフトする幅は引数として指定できる。[[#注意事項]]も参照。

 x = y << 2;

この例では、''y'' を2桁左に算術シフトした結果を ''x'' に格納する。

1ビットの左算術シフトは2倍するのと同じである。1ビットの右算術シフトは、'''値が非負であれば'''2で割ってあまりを捨てるのと同じである。

負の値を右に算術シフトした場合は、シフトしてあふれたビットが1なら（複数シフトの場合は、あふれたビットの中に1がある場合には）、結果に1を足せば、2または2のべきで割ってあまりを捨てるのと同じになる。

=== 論理シフト ===
<!--
[[Image:LogicalShiftRight.JPG|thumb|Right logical shift]]
-->
論理シフトでは、右シフトのときも空いたビットをゼロにする。他は算術シフトと同様である。したがって、論理シフトは符号無しの二進数を扱うのに適していて、算術シフトは[[2の補数]]表現の符号付き二進数を扱うのに適している。
<!-- br clear=all -->

=== (キャリーなし)ローテート ===
<!--images placed next to each other as text is currently so short
{| align=right border=0 cellpadding=0 cellspacing=0
|[[Image:RotateRight.JPG|thumb|Right circular shift or rotate]]
|[[Image:RotateLeft.JPG|thumb|Left circular shift or rotate]]
|}
-->
もうひとつのシフトとして'''環状シフト'''または'''ビット・ローテーション'''がある。これはビット列の左端と右端がつながっているように扱ってシフトするものである。シフト方向の端をあふれた桁は逆の端に置かれる。これは、存在するビットを残しておく必要があるとき、ビットの位置を変えるのに使われたりする。

<!-- br clear=all -->

=== キャリーつきローテート ===
<!--images placed next to each other as text is currently so short-->
{| align=right border=0 cellpadding=0 cellspacing=0
|[[Image:Rotate_right_through_carry.svg|thumb|キャリーつき右ローテート]]
|[[Image:Rotate_left_through_carry.svg‎|thumb|キャリーつき左ローテート]]
|}
こちらはローテート操作の際に、（キャリー）フラグを挟んで、ビット列の左端と右端がつながっているように扱う。フラグに最上位ビットのコピーを入れておけば算術シフトを、0を入れておけば論理シフトをシミュレートできることから、[[PIC (コントローラ)|PIC]]のような[[マイクロコントローラ]]ではローテートとキャリー付きローテートだけを用意して、算術シフトや論理シフト命令は用意しないものもある。キャリー付きローテートは特にプロセッサのレジスタのビット幅より大きな数値のシフトを実現する場合に便利である。

== 使用例 ==
マシンは算術演算や論理演算をするのに十分な命令を持っているが、実際全ての演算はビット演算の組み合わせと何らかのゼロ判定機能があれば実現できる。例えば、下記の例はふたつの任意の整数 '''a''' と '''b''' の乗算をビットシフトと加算で実現する[[擬似コード]]である。
 c := 0
 '''while''' b &ne; 0
     '''if''' b '''and''' 1 &ne; 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ビットは値を残すための配慮である。以下に例を示す。
<source lang="csharp">
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);
    }
}</source>
一方、C, C++ の標準では、このような場合の結果は未定義となっている。

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

== 関連項目 ==
* [[ブール代数]]
* [[論理ゲート]]
* [[論理演算]]
* [[マスク (情報工学)]]

[[Category:プログラミング言語の構文|ひっとえんさん]]
[[Category:コンピュータの算術|ひっとえんさん]]