C言語編 第49章 ビット演算

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

ビット演算

普通の + や - などの演算子による演算は、言うなれば、人間に取って直感的な計算を行います。 これは、「10+1」ならば「11」になるし、「10-1」ならば「9」になるという当たり前の結果を返してくれます。

しかし、コンピュータはデータを 2進数で扱っていますから、2進数で演算が行える方が自然で効率的かも知れません。 この章で説明するビット演算子は、その名の通り、ビット単位での演算を行うための演算子です。 ビットとは、2進数で 1桁分の大きさを指す単位でした(第19章参照

ビット積(AND演算)

ビット積は、ビット同士を比較したとき、両者がともに 1 のときにだけ、結果が 1 となるビット演算です。 いずれか一方、もしくは両方ともが 0 であれば、結果は 0 になります。
「積」なので乗算の考え方です。 掛ける数、掛けられる数のいずれか一方でも 0 ならば、結果も 0 になるのと同じです。

どこかで見たような定義に思えるかも知れませんが、考え方自体は条件式で使う && と同じです。 しかし、目的とするところはまったく別物です。
&&演算子は、条件分岐において、真と偽の判定結果を操作するものでしたが(第13章参照)、 ビット演算子は、ビットの中身を操作するものです。

ビット積の演算子は & です。2つ並べると論理積で、1つだけならビット積になります。 幾つか試してみましょう。

#include <stdio.h>

void andTest(int a, int b);

int main(void)
{
	andTest( 0x0f, 0x01 );
	andTest( 0x0f, 0x0f );
	andTest( 0x0f, 0x00 );
	andTest( 0x0f, 0x07 );

	return 0;
}

void andTest(int a, int b)
{
	printf( "0x%02x & 0x%02x => 0x%02x\n", a, b, (a & b) );
}

実行結果

0x0f & 0x01 => 0x01
0x0f & 0x0f => 0x0f
0x0f & 0x00 => 0x00
0x0f & 0x07 => 0x07

ビット演算を使う場合、ソースコード上でも2進数で記述できると分かりやすいのですが、C言語ではそれができませんから、 代わりに16進数で記述することが多いです。 慣れてくれば、「0x0f」という数値を見た瞬間に、4個のビットが 1 になっている状態が頭に浮かぶようになります。 こうなってしまえば、16進数での記述に不便は感じなくなるでしょう(最初のうちは大変ですが)

実行結果を検討してみましょう。 まず、左辺側は常に 0x0f に固定してあります。これは 2進数で言えば「00001111」です。
最初のパターンでは 0x01 とのビット積を取っていますから、「00001111」&「00000001」となります。 一方だけでも 0 になっているビットは、結果も 0 になりますから、「00000001」が結果になります。 他も同様に考えられます。

では、次のようにしたらどういう結果になるでしょう?

andTest( 0x0f, 0xaa );

2進数の表記に直すと、「00001111」&「10101010」となります。 各ビットを比較し、一方だけでも 0 なら結果も 0、両方とも 1 なら結果は 1 というルールで考えていくと、 「00001010」という結果になります。

この結果をよく観察してみると、右辺側の上位 4bit にあった 1 が、すべて 0 に置き換わったことが分かります。 実はこれがビット積の重要な使い道なのです。 一般に「マスクを取る」と呼ばれるこの手法は、不要なビットを 0 に変えるという効果があります。
つまり、0 にしたい部分を 0 に、元のまま残しておきたい部分を 1 にしたビット列を用意し、 そのビット列と対象のビット列とのビット積を取るのです。

下位4bit を 0 にしたければ、「11110000」とのビット積を取ればよく、 下位2bit ならば、「11111100」とのビット積を取ればよいということです。


また、AND演算は、あるビットに 1 が立っているかを調べるという目的にも使えます。 例えば、16bit の整数の最上位ビットが 1 かどうか調べるには、次のようにします。

if( num & 0x80 ){
	/* 最上位ビットは 1 */
}

最上位ビットが 1 であれば、マスクを取った結果は「10000000」となり、 1 でなければ、結果は「00000000」となります。
前者は、0以外の整数なので真となり、後者は 0 なので偽となる訳です。

ビット和(OR演算)

ビット和は、ビット同士を比較したとき、一方だけでも 1 のときに、結果が 1 となるビット演算です。 両方ともが 0 であれば、結果は 0 になります。
「和」なので加算の考え方です。 足される数、足す数が両方とも 0 なら、結果も 0 です。

ビット和の演算子は | です。2つ並べると論理和で、1つだけならビット和になります。 幾つか試してみましょう。

#include <stdio.h>

void orTest(int a, int b);

int main(void)
{
	orTest( 0x0f, 0x01 );
	orTest( 0x0f, 0x0f );
	orTest( 0x0f, 0x00 );
	orTest( 0x0f, 0x07 );
	orTest( 0x0f, 0xaa );

	return 0;
}

void orTest(int a, int b)
{
	printf( "0x%02x | 0x%02x => 0x%02x\n", a, b, (a | b) );
}

実行結果

0x0f | 0x01 => 0x0f
0x0f | 0x0f => 0x0f
0x0f | 0x00 => 0x0f
0x0f | 0x07 => 0x0f
0x0f | 0xaa => 0xaf

前の項での andTest関数と同じ値を使って、今度は OR演算を行っています。

ビット和は、一方だけでも 1 になっているビットは、結果も 1 になります。
例えば、「00001111」|「10101010」であれば、「10101111」になります。 この結果は、左辺と右辺の値の中で、1 になっている部分が合体したような状態です。

このようにビット和は、任意のビットに 1 を立てるような目的で使うことができます

ビット否定(NOT演算)

ビット否定は、ビットが 0 になっている箇所を 1 に、1 になっている箇所を 0 にする演算です。
「否定」なので、値を逆転させるような考え方です。

ビット否定の演算子は ~ です。 ビット否定演算子は、これまでのビット積や、ビット和とは異なり、左辺と右辺を持つ演算子ではありません。

#include <stdio.h>

void notTest(int a);

int main(void)
{
	notTest( 0x00 );
	notTest( 0x01 );
	notTest( 0x07 );
	notTest( 0xF0 );
	notTest( 0xFF );

	return 0;
}

void notTest(int a)
{
	printf( "~0x%08x => 0x%08x\n", a, ~a );
}

実行結果

~0x00000000 => 0xffffffff
~0x00000001 => 0xfffffffe
~0x00000007 => 0xfffffff8
~0x000000f0 => 0xffffff0f
~0x000000ff => 0xffffff00

ビット否定は、すべてのビット(1つ1つのビット)を、0 なら 1 に、1 なら 0 にひっくり返します。


あるビット列 a に対して NOT演算を行った結果 ~a があるとき、 「a | ~a」のように、OR演算で結合すると、全てのビットが 1 になります。
このように、ビット演算はうまく組み合わせることで、複雑な操作を実現できることがあります。

排他的論理和(XOR演算)

排他的論理和は、ビット同士を比較したとき、いずれか一方だけが 1 のときに結果が 1 になるビット演算です。
OR演算と異なり、両方ともが 1 の場合には、結果が 0 になります。

排他的論理和の演算子は ^ です。 幾つか試してみましょう。

#include <stdio.h>

void xorTest(int a, int b);

int main(void)
{
	xorTest( 0x0f, 0x01 );
	xorTest( 0x0f, 0x0f );
	xorTest( 0x0f, 0x00 );
	xorTest( 0x0f, 0x07 );
	xorTest( 0x0f, 0xaa );

	return 0;
}

void xorTest(int a, int b)
{
	printf( "0x%02x ^ 0x%02x => 0x%02x\n", a, b, (a ^ b) );
}

実行結果

0x0f ^ 0x01 => 0x0e
0x0f ^ 0x0f => 0x00
0x0f ^ 0x00 => 0x0f
0x0f ^ 0x07 => 0x08
0x0f ^ 0xaa => 0xa5

XOR演算では、比較するビットが同一の部分は、その結果は 0 になりますから、 最初の4つの実行例では、結果の上位4bit がすべて 0000 になっています。

XOR演算には、2度繰り返すと、元の値に戻るという特性があります。

#include <stdio.h>

void xorTest(int a, int b);

int main(void)
{
	xorTest( 0x0f, 0x01 );
	xorTest( 0x0f, 0x0f );
	xorTest( 0x0f, 0x00 );
	xorTest( 0x0f, 0x07 );
	xorTest( 0x0f, 0xaa );

	return 0;
}

void xorTest(int a, int b)
{
	int ans = a ^ b;

	printf( "0x%02x ^ 0x%02x => 0x%02x\n", a, b, ans );
	printf( "0x%02x ^ 0x%02x => 0x%02x\n", ans, b, (ans ^ b) );
	printf( "\n" );
}

実行結果

0x0f ^ 0x01 => 0x0e
0x0e ^ 0x01 => 0x0f

0x0f ^ 0x0f => 0x00
0x00 ^ 0x0f => 0x0f

0x0f ^ 0x00 => 0x0f
0x0f ^ 0x00 => 0x0f

0x0f ^ 0x07 => 0x08
0x08 ^ 0x07 => 0x0f

0x0f ^ 0xaa => 0xa5
0xa5 ^ 0xaa => 0x0f

このように、「a ^ b」の結果 c に対して、「c ^ b」とすると a に一致します。 この特性は、ごく簡易的な暗号の仕組みとして利用できます(アルゴリズムとデータ構造編【その他】第3章参照

シフト演算

シフト演算は、ビット列をずらす操作を行います。

シフト演算には、左方向に(上位桁に向かって)ずらす左シフト演算と、 右方向に(下位桁に向かって)ずらす右シフト演算とがあります。 それぞれ、<<演算子と、>>演算子を使います。

例えば、「10010111 << 3」であれば、「10111000」という結果になります。 左辺のビット列を、右辺のビット数分だけずらしている訳ですが、 この結果が示すように、左シフトした結果、空いたビットには 0 が埋められます。

一方、「10010111 >> 3」の結果が「00010010」になるかというと、その保証はありません。
まず、>>演算子の左辺にある「10010111」が、符号無し整数であれば、結果は「00010010」になります。これは保証されています。
左辺の「10010111」が符号付き整数の場合は、「00010010」になるかも知れないし、ならないかも知れません。 このように保証されないのは、符号付き整数には符号ビットというものが含まれており、これも一緒にシフトされてしまうと、データが壊されてしまうためです。

なお、右辺の値は 0以上でなくてはならず、負数を指定した場合の動作は未定義です。 右辺が 0 の場合の結果は、左辺の値のままです。

#include <stdio.h>

void lShiftTest(unsigned int a, int b);
void rShiftTest(unsigned int a, int b);

int main(void)
{
	lShiftTest( 0x0f, 1 );
	lShiftTest( 0x0f, 4 );
	lShiftTest( 0x0f, 5 );
	rShiftTest( 0x0f, 1 );
	rShiftTest( 0x0f, 4 );
	rShiftTest( 0x0f, 0 );

	return 0;
}

void lShiftTest(unsigned int a, int b)
{
	printf( "0x%02x << %d => 0x%02x\n", a, b, (a << b) );
}

void rShiftTest(unsigned int a, int b)
{
	printf( "0x%02x >> %d => 0x%02x\n", a, b, (a >> b) );
}

実行結果

0x0f << 1 => 0x1e
0x0f << 4 => 0xf0
0x0f << 5 => 0x1e0
0x0f >> 1 => 0x07
0x0f >> 4 => 0x00
0x0f >> 0 => 0x0f

5bit の左シフトをした結果は桁が増えていますが、これは 32bit の int型を使っているためです。 16bit の変数であれば、上位の桁はカットされて、0xe0 になります。

右シフトの場合、下位のビットが削られていくのが分かります。 空いた上位ビットには、0 が埋められていますが、先ほど説明したように、左辺側が負数の場合には、保証されません。


シフト演算は、乗算や除算の代わりとなることがあります。 1ビット左シフトするたびに 2倍に、1ビット右シフトするたびに 2分の1 になっていきます。

#include <stdio.h>

int main(void)
{
	int num;

	num = 1;

	num = num << 1;
	printf( "%d\n", num );
	num = num << 1;
	printf( "%d\n", num );
	num = num << 1;
	printf( "%d\n", num );

	num = num >> 1;
	printf( "%d\n", num );
	num = num >> 1;
	printf( "%d\n", num );
	num = num >> 1;
	printf( "%d\n", num );

	return 0;
}

実行結果

2
4
8
4
2
1

シフト演算は、乗算や除算よりも高速に行えることもあります。

複合代入演算子

ここまでに紹介した各演算子には、複合代入演算子(第27章)も存在しています。 すなわち、

があります。 NOT演算子は、左辺と右辺を持つ演算子ではないので、~= という演算子はありません。


練習問題

問題@ int型の変数num に 0 が格納されていたら 1 に、1 が格納されていたら 0 に変換するとします。 0 か 1 しか格納されている可能性がないとすれば、if文を使って次のように書けます。

if( num == 0 ){
	num = 1;
}
else{
	num = 0;
}

これと同じことを、if文を使わずに、ビット演算だけで書き換えて下さい。

問題A ある正の整数に、1 が立っているビットが幾つあるかを調べるプログラムを作成して下さい。

問題B 次の関数は何をしているでしょうか。

int func(int a, int b)
{
	return ( ( a | b ) & ~( a & b ) );
}

問題C 標準入力から受け取った 10進数の正の整数を、2進数の表記で標準出力へ出力するプログラムを作成して下さい。


解答ページはこちら

参考リンク

更新履歴

'2012/5/25 「XOR演算」の項から、アルゴリズムとデータ構造編へのリンクを追加。

'2011/2/6 新規作成。



前の章へ

次の章へ

C言語編のトップページへ

Programming Place Plus のトップページへ