ビット演算
デジタルコンピュータの内部では、情報をビット列として表しており、CPUやMPUなどにはビット演算用の命令が多種用意されている。特に機械語のプログラムでは多用される演算であり、高水準言語のソースコードでは直接記述されていない場合でも結局機械語に変換されて実行されるので、内部的に多用されている。
ビット演算は大きく分けて次のように二種類ある。
ビット単位の論理演算
NOT, AND, OR, XORがある。
ビットの位置を入れ替える操作
大きく分けるとシフト演算(一方向に単純に移動させる操作)とローテート演算(ビット列の先頭と末尾を繋いだように循環させる操作(「循環シフト」「環状シフト」「ビット回転」とも)がある。
実装の観点からは、現在一般的なエレクトロニクス式デジタルコンピュータでは、加減算ではビットあたり数個程度の論理ゲートに加え多少複雑なキャリー伝搬の処理が、乗除算では多段に渡る処理が必要であるのに対し、ビット演算は1個か高々2個の論理ゲートで行えるため、多くの場合、最短サイクルしか必要としない。(つまりビット演算は、CPUの演算の中でも特に高速に行われる。)そのことから、高性能なプログラムを実現するための機械語コーディングではビット演算の使いこなしは重要なテクニックである。また内部的には論理演算はALUで、(多桁の)シフトはバレルシフタで演算される。
算術シフトでは、右シフトにおいて、最上位ビット(2の補数表現であれば符号ビット)は保存される。左シフトは、(一部例外を除き)後述する論理シフトと同じもので、空くビット位置にはゼロが入る。このシフトではあふれたビットは単に消える(プロセッサの実装によってはフラグに入るものもある)。下記の例は 4ビットレジスタの場合である。
前者の例は、左端の0はあふれて消え、あらたな0が右端に入れられている。後者の例は、右端の1はあふれて消え、符号ビット1が左端にコピーされている。あふれたビットは、多くの場合キャリーフラグにセットされる。マルチプルシフトは、シングルシフトをくりかえしたものと同じ結果になる。
C/C++では、左シフトと右シフトは "<<" と ">>" で表される。シフトする幅は右オペランドにより指定できる。#注意事項も参照。
この例では、y を2桁左に算術シフトした結果を x に格納する。
1ビットの左算術シフトは2倍するのと同じである。1ビットの右算術シフトは、値が非負であれば2で割ってあまりを捨てるのと同じである。
負の値を右に算術シフトした場合は、シフトしてあふれたビットが1なら(複数シフトの場合は、あふれたビットの中に1がある場合には)、結果に1を足せば、2または2のべきで割ってあまりを捨てるのと同じになる。