p.218 のビットベクトルを用いた方法の理解

[konabe]

@ChanPoyu

question1_bitvector.cpp

boolean配列の代わりに、ビットでフラグ立ててるだけって感じっぽい。 例えば y ||= 1 << x　だったら変数yのx+1bit目のフラグを立てるっていう意味になる。

rks-Mac:Chapter1 rk$ g++ question1_bitvector.cpp && ./a.out 

isUniqueChars(pythonista) is called
iter = 0 | str(0) = p
val(b):         00000000000000000000000000001111
1 << val(b):    00000000000000001000000000000000
checker(b)      00000000000000001000000000000000
iter = 1 | str(1) = y
val(b):         00000000000000000000000000011000
1 << val(b):    00000001000000000000000000000000
checker(b)      00000001000000001000000000000000
iter = 2 | str(2) = t
val(b):         00000000000000000000000000010011
1 << val(b):    00000000000010000000000000000000
checker(b)      00000001000010001000000000000000
iter = 3 | str(3) = h
val(b):         00000000000000000000000000000111
1 << val(b):    00000000000000000000000010000000
checker(b)      00000001000010001000000010000000
iter = 4 | str(4) = o
val(b):         00000000000000000000000000001110
1 << val(b):    00000000000000000100000000000000
checker(b)      00000001000010001100000010000000
iter = 5 | str(5) = n
val(b):         00000000000000000000000000001101
1 << val(b):    00000000000000000010000000000000
checker(b)      00000001000010001110000010000000
iter = 6 | str(6) = i
val(b):         00000000000000000000000000001000
1 << val(b):    00000000000000000000000100000000
checker(b)      00000001000010001110000110000000
iter = 7 | str(7) = s
val(b):         00000000000000000000000000010010
1 << val(b):    00000000000001000000000000000000
checker(b)      00000001000011001110000110000000
iter = 8 | str(8) = t
val(b):         00000000000000000000000000010011
1 << val(b):    00000000000010000000000000000000

[konabe]

例えば 'a'がきたら、abcd...zの0番目なので、0bit目を立てる 'c'がきたら、abcd...zの2番目なので、2bit目を立てる やってることはbooleanの配列と本質的に変わらなかったｗ

[konabe]

僕が最初に知ったかぶりで思いついてたのは、 整数を全部binaryとみなして、 binaryのうちのbitが一つでも違ってたら違うよねみたいなことだったけど、これは効率悪いねｗ

[konabe]

http://proger.blog10.fc2.com/blog-entry-28.html ここにも書いてあるとおり、 boolean型のサイズは1byte=8bitで、8bit x （文字集合の大きさ） この方法でやると、1bit x （文字集合の大きさ） ってなるから、メモリ消費が８分の１ってなるわけか。 文字集合が十分に大きい（int型のサイズよりも大きい）場合は話が変わるけどｗ

[konabe]

ここから学べることは、 int型の変数に||= (1 << x)ってしてたらbinaryフラグを使ってる可能性が高いということｗ