2013年1月14日月曜日

ビット(bit)演算操作の覚え書き


プログラミングをする上でビットの操作の理解は必須である。

これだけは覚えておきたい基礎となるポイントをまとめておく。

これより先、0101などの0、1の羅列はすべて2進数とする。

見やすさ優先で頭に0bつけない。


◆ 手動でのビット操作

(1)
Q.
0110 + 0110 + 0110 + 0110

A.

11000
10進数と同じように考えればよい。
0110が4つあるので、×4で2ビットシフトさせた、と考えてもいい。


(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個左シフトすることである。
これは2倍を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までをクリアする。
例えば、
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(GByte)
= 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個である。



0 件のコメント:

コメントを投稿