RSS
Programming Place Plus トップページ – Ｃ言語編
この章の概要です。
計算をビット単位で行う方法があると、効率的な演算が行えることがあります。このような演算を、ビット演算と呼びます。
ビット演算では、+、-、*、/ といった演算子は使いません。代わりに、ビット演算子を使います。この章では、Ｃ言語に用意されているすべてのビット演算子を取り上げます。
なお、ビット演算子が適用できるのは、整数型に対してだけです。
また、強制されるわけではありませんが、符号無し整数型に限って使うようにした方がトラブルが少なくて済みます。符号付き整数の値を表現するとき、最上位ビットが符号の意味をもっていることが多いため（「コンピュータサイエンス編＞基数」のページを参照）、このビットを巻き込んだビット演算はトラブルが起こりやすいためです。
ビット積（AND）は、２つのビットを比較して、両者がともに 1 のときにだけ、結果が 1 となるビット演算です。いずれか一方、もしくは両方ともが 0 であれば、結果は 0 です。
ビット「積」なので、乗算の考え方をしています。「1 * 1」なら「1」になるし、「1 * 0」のように一方だけでも 0 なら 0 になるということです。
ビット積の演算子は & です。
結果がなる整数型になる式 & 結果がなる整数型になる式いつものように、通常の算術型変換（第２１章）が行われ、変換後の型が結果の型になります。
いくつか試してみましょう。
#include <stdio.h>
void andTest(unsigned int a, unsigned int b);
int main(void)
{
andTest( 0x0f, 0x01 );
andTest( 0x0f, 0x0f );
andTest( 0x0f, 0x00 );
andTest( 0x0f, 0xaa );
andTest( 0x0f, 0xff );
return 0;
}
void andTest(unsigned int a, unsigned int b)
{
printf( "0x%02x & 0x%02x => 0x%02x\n", a, b, (a & b) );
}実行結果
0x0f & 0x01 => 0x01
0x0f & 0x0f => 0x0f
0x0f & 0x00 => 0x00
0x0f & 0xaa => 0x0a
0x0f & 0xff => 0x0fビット演算を使う場合、ソースコード上でも 2進数で記述できると分かりやすいのですが、Ｃ言語ではそれができませんから、代わりに 16進数で記述することが多いです。
実行結果を検討してみましょう。まず、左辺側はつねに 0x0f に固定してあります。これは 2進数では「00001111」です。
最初のパターンでは 0x01 とのビット積を取っています。これは「00001111」&「00000001」ということです。どちらか一方だけでも 0 になっているビットは、0 になりますから、結果は「00000001」です。他もパターンも同様に考えられます。
５つのパターンの結果をそれぞれよく観察してみると、右辺側の上位 4ビットにあった 1 が、すべて 0 に置き換わったことが分かります。そして、下位 4ビットの並びにはの変化がありません。
これがビット積の特徴で、最も重要な使い方を示しています。つまり、0 にしたい部分を 0 に、元のまま残しておきたい部分を 1 にしたビット列を用意し、そのビット列と対象のビット列とのビット積を取るのです。これは一般に「マスクを取る」と呼ばれる手法です。
もし、下位4ビットを 0 にしたければ、「11110000」とのビット積を取ればよいですし、下位2ビットを 0 にしたいならば、「11111100」とのビット積を取ればよいということです。もっと複雑に、偶数ビットだけを 0 にしたいのなら「01010101」とビット積を取れば実現できます。
また、ビット積は、あるビットに 1 が立っているかを調べるという目的にも使えます。たとえば、16ビットの整数の最上位ビットが 1 かどうか調べるには、次のようにします。
if( num & 0x80 ){
// 最上位ビットは 1
}最上位ビットが 1 であれば、0x80 つまり「10000000」とビット積を行った結果は「10000000」です。そうでなければ「00000000」です。前者の結果を得た場合、それは 0以外の値なので真ですし、後者の結果を得た場合、それは 0 なので偽です。
ビット和（OR）は、２つのビットを比較して、一方だけでも 1 のときに、結果が 1 となるビット演算です。両方ともが 0 であれば、結果は 0 です。
ビット「和」なので、加算の考え方をしています。「0 + 0」では「0」のままですが、「1 + 0」のように一方だけでも 1 なら 1 になります。「1 + 1」だけ違いますが、上限値で頭打ちしていると考えればよいでしょうか。
ビット和の演算子は | です。
結果がなる整数型になる式 | 結果がなる整数型になる式いつものように、通常の算術型変換（第２１章）が行われ、変換後の型が結果の型になります。
いくつか試してみましょう。
#include <stdio.h>
void orTest(unsigned int a, unsigned int b);
int main(void)
{
orTest( 0x0f, 0x01 );
orTest( 0x0f, 0x0f );
orTest( 0x0f, 0x00 );
orTest( 0x0f, 0xaa );
orTest( 0x0f, 0xff );
return 0;
}
void orTest(unsigned int a, unsigned int b)
{
printf( "0x%02x | 0x%02x => 0x%02x\n", a, b, (a | b) );
}実行結果
0x0f | 0x01 => 0x0f
0x0f | 0x0f => 0x0f
0x0f | 0x00 => 0x0f
0x0f | 0xaa => 0xaf
0x0f | 0xff => 0xff前の項での andTest関数と同じ値を使って、今度はビット和演算を行っています。
たとえば、１つ目のパターンでは、「00001111」と「00000001」のビット和演算です。両方のビットが 0 のところだけ 0 のままで、ほかのビットは 1 になりますから、「00001111」という結果が得られます。
「00001111」|「10101010」であれば、「10101111」になります。この結果を観察すると、左辺と右辺の値の中で、1 になっている部分が合体したような状態です。
ビット和は、任意のビットに 1 を立てるような目的で使えます。たとえば、上位 4ビットにまとめて 1 を立てたいときには、「11110000」とのビット和を取ればよい訳です。同様に、偶数ビットをすべて 1 にしたければ、「10101010」とのビット和を取れば実現できます。
ビット否定（NOT）は、ビットが 0 になっている箇所を 1 に、1 になっている箇所を 0 にする演算です。
ビット否定の演算子は ~ です。ビット演算子の中で唯一、オペランドが１つだけの演算子です。
~結果がなる整数型になる式オペランドの型は、整数拡張（第２１章）によって拡張され、結果の型もこれと同じになります。
いくつか試してみましょう。
#include <stdio.h>
void notTest(unsigned int a);
int main(void)
{
notTest( 0x00 );
notTest( 0x01 );
notTest( 0x07 );
notTest( 0xF0 );
notTest( 0xFF );
return 0;
}
void notTest(unsigned int a)
{
printf( "~0x%08x => 0x%08x\n", a, ~a );
}実行結果
~0x00000000 => 0xffffffff
~0x00000001 => 0xfffffffe
~0x00000007 => 0xfffffff8
~0x000000f0 => 0xffffff0f
~0x000000ff => 0xffffff00ビット否定は、すべてのビット（１つ１つのビット）を、0 なら 1 に、1 なら 0 にひっくり返します。これはシンプルで分かりやすいと思います。
unsigned char型や unsigned short型を使う際には注意が必要です。これらの型は演算の際に、整数拡張によって (singed の) int型に変換されます（第２１章）。そのため、符号ビットの部分が反転されてしまい、意図しない結果を生む恐れがあります。
unsigned char型や unsigned short型に対してビット演算を行うのなら、キャストによって本来の型で扱うことを明示しましょう。
#include <stdio.h>
int main(void)
{
unsigned char uc = 0x0f;
printf( "%d\n", ~uc >= 0x0f );
printf( "%d\n", (unsigned char)(~uc) >= 0x0f );
return 0;
}実行結果
0
1unsigned char型へのキャストを行わないと、「~uc >= 0x0f」の結果が偽になってしまいます。整数拡張で signed int型に変換されて「0x0000000f」（32bit を仮定）になり、これをビット否定して「0xfffffff0」となるからです。符号付き整数型ですから、これは負数（２の補数なら -16）なので、「-16 >= 0x0f」という比較になってしまいます。これは偽です。
最後に、ビット否定演算の特徴的な性質を１つ挙げておきます。
あるビット列 a に対して、ビット否定演算を行った結果 ~a があるとき、「a | ~a」のように、OR演算で結合すると、すべてのビットが 1 になります。
また、「~0」のように表記することで、すべてのビットが 1 の整数値を得られることが利用されるケースがあります。たとえば、次の２つの宣言は同じ意味でしょうか？
unsigned int n1 = 0xffffffff;
unsigned int n2 = ~0;n1 の方は、unsigned int が 32ビットであることを想定してしまっています。もし 64ビットの環境だったら、上位の 32ビットは 0 になります。対して n2 の方は、unsigned int型の大きさがいくらであっても、必ず全ビットが 1 の数値で初期化できます。
排他的論理和（XOR、EOR）は、２つのビット同士を比較して、いずれか一方だけが 1 のときに結果が 1 になるビット演算です。ここではビット単位の話をするので、ビット単位の排他的論理和とか、排他的ビット和と呼ぶ方が適切ですが、単に排他的論理和と呼ぶことも多いです。
排他的論理和の演算子は ^ です。
結果がなる整数型になる式 ^ 結果がなる整数型になる式いつものように、通常の算術型変換（第２１章）が行われ、変換後の型が結果の型になります。
いくつか試してみましょう。
#include <stdio.h>
void xorTest(unsigned int a, unsigned int b);
int main(void)
{
xorTest( 0x0f, 0x01 );
xorTest( 0x0f, 0x0f );
xorTest( 0x0f, 0x00 );
xorTest( 0x0f, 0xaa );
xorTest( 0x0f, 0xff );
return 0;
}
void xorTest(unsigned int a, unsigned int b)
{
printf( "0x%02x ^ 0x%02x => 0x%02x\n", a, b, (a ^ b) );
}実行結果
0x0f ^ 0x01 => 0x0e
0x0f ^ 0x0f => 0x00
0x0f ^ 0x00 => 0x0f
0x0f ^ 0xaa => 0xa5
0x0f ^ 0xff => 0xf0排他的論理和では、比較するビットが同一の部分だけが 0 になります。最初の４つの実行例では、互いに上位 4ビットが 0 なので、結果の上位 4ビットもすべて 0 になっています。
排他的論理和には、２度繰り返すと、元の値に戻るという特性があります。
#include <stdio.h>
void xorTest(unsigned int a, unsigned int b);
int main(void)
{
xorTest( 0x0f, 0x01 );
xorTest( 0x0f, 0x0f );
xorTest( 0x0f, 0x00 );
xorTest( 0x0f, 0xaa );
xorTest( 0x0f, 0xff );
return 0;
}
void xorTest(unsigned int a, unsigned int b)
{
unsigned 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 ^ 0xaa => 0xa5
0xa5 ^ 0xaa => 0x0f
0x0f ^ 0xff => 0xf0
0xf0 ^ 0xff => 0x0fこのように、「a ^ b」の結果 c に対して、「c ^ b」とすると a に一致します。この特性は、ごく簡易的な暗号の仕組みとして利用できます（アルゴリズムとデータ構造編【その他】第３章参照）
シフト演算には、左方向に（上位桁に向かって）ずらす左シフト演算と、右方向に（下位桁に向かって）ずらす右シフト演算とがあります。それぞれ、<<演算子と、>>演算子を使います。
結果が整数型になる式 << 結果が整数型になる式
結果が整数型になる式 >> 結果が整数型になる式左オペランドのビット列を、右オペランドの値の数だけずらします。
２つのオペランドには、整数拡張（第２１章）が適用されます。シフト演算を終えた後の結果の値は、左オペランドに整数拡張がなされた後の型になります。
整数拡張された後の型のビット数以上の値を右オペランドに指定した場合と、右オペランドに負数を指定した場合は、未定義の動作になります。
「10010111 << 3」であれば、各ビットが左方向に 3ビットずらされ「10111000」という結果になります。左シフトした結果、空きになった右側のビットには 0 が埋められます。
一方、「10010111 >> 3」であれば、各ビットが右方向に 3ビットずらされ「00010010」という結果になります。ただし、これが保証されるのは、左オペランドが負でないときに限られます。負数を右シフトした場合、空きになった左側のビットに 0 が入るのか 1 に入るのかは、処理系定義です。
いくつか試してみましょう。
#include <stdio.h>
void lShiftTest(unsigned int a, unsigned int b);
void rShiftTest(unsigned int a, unsigned 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, unsigned int b)
{
printf( "0x%02x << %u => 0x%02x\n", a, b, (a << b) );
}
void rShiftTest(unsigned int a, unsigned int b)
{
printf( "0x%02x >> %u => 0x%02x\n", a, b, (a >> b) );
}実行結果
0x0f << 1 => 0x1e
0x0f << 4 => 0xf0
0x0f << 5 => 0x1e0
0x0f >> 1 => 0x07
0x0f >> 4 => 0x00
0x0f >> 0 => 0x0f5ビットの左シフトをした結果は桁が増えていますが、これは 32ビットの int型を使っているためです。16ビットの変数であれば、上位の桁はカットされて、0xe0 になります。
右シフトの場合、下位のビットが削られていくのが分かります。空いた上位ビットには、0 が埋められていますが、先ほど説明したように、左辺側が負数の場合には、保証されません。
シフト演算は、乗算や除算の代わりとなることがあります。2進法の性質からいって、1ビット上位に動くと、10進法での 2倍に相当するので、1ビット左シフトするたびに 2倍、1ビット右シフトするたびに 2分の1 を意味します。
#include <stdio.h>
int main(void)
{
unsigned int num = 1;
num = num << 1;
printf( "%u\n", num );
num = num << 1;
printf( "%u\n", num );
num = num << 1;
printf( "%u\n", num );
num = num >> 1;
printf( "%u\n", num );
num = num >> 1;
printf( "%u\n", num );
num = num >> 1;
printf( "%u\n", num );
return 0;
}実行結果
2
4
8
4
2
1シフト演算は、乗算や除算よりも高速に行えることもあり、昔はよく最適化の一環で使われることがありました。現代のコンパイラは優秀なので、このような手法を人間が手動で行うことにはほぼ意味がありません。普通の感覚でいえば、「*8」よりも「<< 3」の方が読みやすいなどということはないので、素直に乗算や除算を使えば良いでしょう。
ここまでに紹介した各演算子には、対応する複合代入演算子（第２７章）もあります。すなわち、
があります。ビット否定演算子だけは、オペランドが１つの演算子なので、複合代入演算子はありません。
問題① unsigned int型の変数num に 0 が格納されていたら 1 に、1 が格納されていたら 0 に変換する処理を、ビット演算を使って書いてください。
問題② ある正の整数に、1 が立っているビットがいくつあるかを調べるプログラムを作成してください。
問題③ 次の関数は何をしているでしょうか。
int func(unsigned int a, unsigned int b)
{
return ( ( a | b ) & ~( a & b ) );
}問題④ 標準入力から受け取った 10進数の正の整数を、2進法で標準出力へ出力するプログラムを作成してください。
’2018/3/24 全面的に文章を見直し、修正を行った。
’2018/2/21 文章中の表記を統一（bit、Byte -> ビット、バイト）
’2012/5/25 「XOR演算」の項から、アルゴリズムとデータ構造編へのリンクを追加。
’2011/2/6 新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| Twitter でツイート | Twitter をフォロー | LINE で送る |
|
RSS
|
管理者情報 | プライバシーポリシー |