リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。
bit演算子
2進数を使った処理をする時には、bit演算子を用いる。
| bit AND | 3 & 5 0011)2 & 0101)2= 0001)2 |
論理積演算子 if ( a == 1 && b == 2 ) … |
| bit OR | 3 | 5 0011)2 | 0101)2= 0111)2 |
論理和演算子 if ( a == 1 || b == 2 ) … |
| bit NOT | ~5 ~ 00..00,0101)2= 11..11,1010)2 |
論理否定演算子 if ( !a == 1 ) … |
| bit EXOR | 3 ^ 5 0011)2 ^ 0101)2= 0110)2 |
|
| bit 左シフト | 3 << 2 0011)2 << 2 = 001100)2 |
3 * 22 と同じ |
| bit 右シフト | 12 >> 2 1100)2 >> 2 = 11)2 |
12 / 22 と同じ |
#include <stdio.h>
int main() {
// bit演算子と論理演算子
printf( "%d¥n" , 12 & 5 ) ; // 1100 & 0101 = 0100 よって 4が表示される
printf( "%d¥n" , 12 && 0 ) ; // 0が表示 論理演算子とbit演算子の違い
printf( "%d¥n" , 12 | 5 ) ; // 1100 | 0101 = 1101 よって 13が表示される
printf( "%d¥n" , 12 || 0 ) ; // 1が表示
// シフト演算子
printf( "%d¥n" , 3 << 2 ) ; // 12が表示
printf( "%d¥n" , 12 >> 2 ) ; // 3が表示
// おまけ
printf( "%d¥n" , ~(unsigned)12 + 1 ) ; // 2の補数(NOT 12 + 1) = -12
return 0 ;
}
2進数を用いた集合計算
リストによる集合の前に、もっと簡単な集合処理を考える。
最も簡単な方法は、要素に含まれる=1 か 含まれない=0 を配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に1を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、演習課題として穴埋めを含むので注意。
しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報を、整数型で保存しているためメモリの無駄である。
データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。
以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc , ba ∪ bc の計算を行う例である。
// 符号なし整数を uint_t とする。
typedef unsigned int uint_t ;
// uint_tのbit数
#define UINT_BITS (sizeof( uint_t ) * 8)
// 集合の内容を表示
void bit_print( uint_t x ) {
for( int i = 0 ; i < UINT_BITS ; i++ )
if ( (x & (1 << i)) != 0 )
printf( "%d " , i ) ;
printf( "\n" ) ;
}
void main() { // 98,7654,3210
// ba = {1,2,3} = 00,0000,1110
uint_t ba = (1<<1) | (1<<2) | (1<<3) ;
// bb = {2,4,6} = 00,0101,0100
uint_t bb = (1<<2) | (1<<4) | (1<<6) ;
// bc = {4,6,9} = 10,0101,0000
uint_t bc = (1<<4) | (1<<6) | (1<<9) ;
bit_print( ba & bb ) ; // ba ∩ bb = {2}
bit_print( bb & bc ) ; // bb ∩ bc = {4,6}
bit_print( ba | bc ) ; // ba ∪ bc = {1,2,3,4,6,9}
}
このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数探索がある。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。
uint_t prime = 0 ; // 初期値=すべての数は素数とする。
void filter() {
for( int i = 2 ; i < UINT_BITS ; i++ ) {
if ( (prime & (1 << i)) == 0 ) {
// iの倍数には、非素数の目印(1)をつける
for( int j = 2*i ; j < UINT_BITS ; j += i )
prime |= (1 << j) ;
}
}
for( int i = 2 ; i < UINT_BITS ; i++ ) {
// 目印のついていない数は素数
if ( (prime & (1 << i)) == 0 )
printf( "%d\n" , i ) ;
}
}
ミニ課題
最初に示した、配列による集合の set-array.cxx で、配列による和集合、エラトステネスのふるいの処理の一部を記述していない。未完成の部分を埋めて、動作を確認せよ。