プログラミングをする上でビットの操作の理解は必須である。
これだけは覚えておきたい基礎となるポイントをまとめておく。
これより先、0101などの0、1の羅列はすべて２進数とする。
見やすさ優先で頭に0bつけない。
◆ 手動でのビット操作
(1)
Q.
0110 + 0110 + 0110 + 0110
A.
11000
10進数と同じように考えればよい。
0110が4つあるので、×4で２ビットシフトさせた、と考えてもいい。
(2)
Q.
0010 * 0011
A.
0110
10進数と同じように筆算でも使ってやればいい。
0010は2なので1ビットシフトさせた、と考えてもいい。
(3)
Q.
1000 - 0110
A.
0010
手動でするならコンピュータと同じように補数計算しなくとも10進数の時と同じようにやればいい。
これで悩むようなら繰り下がりのある引き算が分かっていない。算数から復習しよう。
(4)
Q.
1101 ^ 0101
^はXORである。
A.
1000
(5)
Q.
1011 & (~0 << 2)
~はnotである。
A.
1000
~0 は 1111 であり、
それを2ビットシフトするので、1100。
下位2ビットをすべて0にしたい場合などに利用できる。
◆ バイト数の設定
256K、256M, 256Gなどのサイズ表現をビットで分かりやすく定義する。
例えばC言語ならこのようなプリプロセッサをよく見かける。
#define SIZE_K (256 << 10) /* 256Kバイト */
#define SIZE_M (256 << 20) /* 256Mバイト */
#define SIZE_G (256 << 30) /* 256Gバイト */
* << 10 とは、*を10個左シフトすることである。
これは２倍を10回(2^10 = 1024)することに等しい。
◆ アラインメント(alignment)
あるアドレスの先頭を4バイトの倍数にアラインメントしたい。
例えば、あるアドレスが6の場合、4にする
| | | |
0 4 8 12
↑
6
どういったコードで表現できるか示す。
PAGE_SIZE = 4
MASK = (1 << 2)-1 # 4 - 1 == 3
address = 6 # アラインメントされていない
excess = address & MASK # 6 % 4 = 2 として余りを求めたと考えてもよい
address -= excess # 4
分かりやすく4バイト単位としたが、OSがページ単位でメモリを管理する場合は
4Kバイトで区切られることが多い。その場合、MASKは下にすればよい。
4 < < 10 - 1
(4 × 1024 - 1)
アラインメントのために、Cのコードで切り下げ、切り上げするマクロをよく見かけることがある。
#define ROUND_DOWN_TO_PAGE_SIZE(p) \
((size_t)(p) & ~(PAGE_SIZE - 1))
#define ROUND_UP_TO_PAGE_SIZE(p) \
(((size_t)(p) + (PAGE_SIZE - 1)) & ~(PAGE_SIZE - 1))
◆ 特定領域のビットのクリア操作
あるビットで表されたnumをiからjまでをクリアする。あるアドレスの先頭を4バイトの倍数にアラインメントしたい。
例えば、あるアドレスが6の場合、4にする
| | | |
0 4 8 12
↑
6
どういったコードで表現できるか示す。
PAGE_SIZE = 4
MASK = (1 << 2)-1 # 4 - 1 == 3
excess = address & MASK # 6 % 4 = 2 として余りを求めたと考えてもよい
address -= excess # 4
分かりやすく4バイト単位としたが、OSがページ単位でメモリを管理する場合は
4Kバイトで区切られることが多い。その場合、MASKは下にすればよい。
4 < < 10 - 1
(4 × 1024 - 1)
アラインメントのために、Cのコードで切り下げ、切り上げするマクロをよく見かけることがある。
#define ROUND_DOWN_TO_PAGE_SIZE(p) \
((size_t)(p) & ~(PAGE_SIZE - 1))
(((size_t)(p) + (PAGE_SIZE - 1)) & ~(PAGE_SIZE - 1))
◆ 特定領域のビットのクリア操作
例えば、
num：10101101
i：2
j：5
結果：10000001
コード例
// jより上位を1に、下位を0にする
// jが5なら~0(=11111111)が11000000になる
int left = ~0 << (j + 1);
// iより下位を1にする
// iが2なら1<<iは100なのでそこから1減算してで011
int right = (1 << i) -1 ;
int mask = left | right;
return num & mask;
◆ ビットを使った整数の管理
ビットマップ(bit map)を使い整数を管理する。ビットベクトル(bit vector)とも呼ばれる。
例えば40億個のint型の整数(4byte)を扱うとする。メモリは1GByteしか利用できない。
int型(4byteとする) × 40億 > 1GByte
byteで比較すると、
4 × 4 * 2^30 > 2^30
2^34(byte) > 2^30(byte)整数1つ1つをint型で扱うと利用可能なメモリをオーバする。しかし各bitに整数を対応させられれば、1GByteは80億bitであるため管理できる。
= 1 × 1024 × 1024 × 1024 × 8(bit)
= 1 × 2^10 × 2^10 × 2^10 × 8(bit)
= 8 × 2^30
= 80億(bit)
さっそくコード例を見てもらおうと思うが、先にコード内で利用したテクニックを説明しておく。
以下のように読み替えてもいい。
num >> 3 ⇒ num / 8
num & 0x7 ⇒ num % 8
例えば10進数の10は
10 / 8 = 1, 10 % 8 = 2 なので
2バイト目(bitset[1])の2ビット目(00000010)に対応する。
(コード例)
char bitset [size >> 3];
int getBit(int num) {
return bitset[ num >> 3 ] & (1 << (num & 0x7));
// 直接整数値を返したい場合は以下でもいいか
// return (num >> 3) * 8 + (num & 0x7)
}
void setBit(int num) {
bitset[ num >> 3 ] |= (1 << (num & 0x7));
}
void clearBit(int num) {
bitset[ num >> 3 ] &= ~(1 << (num & 0x7));
}
このビットマップはbitsetはchar型(1byte)単位で扱っていたが、例えばbitsetをint型にしてもよい。int型が4byteであれば32個ずつ管理できるため下記の変更をする。
num >> 5 ⇒ num / 32
num & 0x1F ⇒ num % 32
また、仮にbit単位で扱える型があればこのような書き方もできただろう。
int getBit(int num) {
return bitset & (1 << num);
}
void setBit(int num) {
bitset | (1 << num);
}
void clearBit(int num) {
bitset & ~(1 << num);
}
(補足)
ビットベクトルを使ってすべてを解決できるわけではない。
例えば、同じく40億(2^32)個の整数を管理する場合であっても、10MByte(2^23バイト程度 ※2^3×2^20)のメモリしか使用できない場合どうなるだろうか。ビットベクトルを使っても足りない。2^23×8=2^26である。
物理的な制約はどうしようもないので、整数をある範囲ごとに区切るしかない。
1つの配列サイズ = 40億(2^32)個 / 整数範囲 <= 10MByte(2^23) / 4 = 2^21
※整数値を4byte(2^2)のint型とすると利用できる配列サイズは1/4になる。
上記から整数範囲は、
2^11 <= 整数範囲
さらに
2^11 <= 整数範囲 <= 10MByte(2^23バイト = 2^26ビット)
間をとって整数範囲を2^20とすると、1つの配列では2^20の整数を扱える。
ビットベクトルを使うと、2^20 × 8 = 2^23個である。
