せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】Rubyの最上位ビットはどこ？　ビットカウントテーブルを使ってビットカウントの巻。

このサイトを参考に、
ビット演算の奥深さを勉強中。
　

レジスタ中の 1 になっているビット数を数えるアルゴリズム

　
今回はビットカウントテーブルを使う方法です。


　

Rubyでのビット符号って？

Rubyの最上位ビット(MSB)はどこ？
　

右シフトは、符号ビット(最上位ビット(MSB))が保持されます。 bitsが実数の場合、小数点以下を切り捨てた値でシフトします。

http://doc.ruby-lang.org/ja/1.9.3/class/Fixnum.html

ビット演算については 2 の補数表現の無限長 のビットストリングとみなすことができます。

　
無限長になってしまったら、符号ビットはどこのビットになるんだ？
　

p 0b1000_0000_0000_0000_0000_0000_0000_0000
p  -11.to_s(2)
p  11.to_s(2)

■実行結果

2147483648
"-1011"
"1011"

ううむよくわからない。
最上位ビット、なんてないように見える。

　

printf("%b",(-0b111))

　
■実行結果

..1001

　
なるほど。

負の数は左側に無限に 1 のビットが立っているように操作できます。

http://doc.ruby-lang.org/ja/1.9.2/class/Bignum.html

これを表現しているのか。
　

printf("%b",(0b11111 & -0b1111))

■実行結果

10001

なるほど。
　
「符号ビットは何ビット目」という概念はなくて、
明示的にマイナスをつける事で負数に出来る。
内部的には１のビットが無限に立つ（＝マイナスをつける以外に表現できない）

という理解。


　

ビットカウントテーブルとは

0 ～ 255 までの 8 ビット分のビットカウントテーブルを作成しておいて、ビットカウントしたデータを 8 ビットづつに区切って処理することになるだろう。

const int BITS_COUNT_TABLE[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

　
ごめんぜんぜん意味分からない。
　
　
もう少し小さなサイズを扱っているページも。

テーブルを使えばもっと速い。
int bitcount(unsigned long n)
{
const static unsigned char aa[] = {
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
};

http://hp.vector.co.jp/authors/VA000092/win32/technique.html

　
なるほど。。
このテーブルは、２進法で書くと、
0 01 10 11
100 101 110 111
1000 1001 1010 1011
1100 1101 1110 1111

こうなる。
つまり、0b1111+1番目まで（配列は０始まり）のONビットの個数を表してるのか！

Rubyで書くと

左シフト演算をしているので、
符号つきの場合を考える必要があるかと思ったけど、上の考察により、
明示的にマイナス符号をつけた値を渡していないので大丈夫そう。

BITS_COUNT_TABLE = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
]
def numofbits2(bits)
    num  = 0
    while bits != 0 do
        num += BITS_COUNT_TABLE[bits & 0b11111111]
        bits >>= 8
    end
    num
end

p numofbits2(0b1000000010100010001010000000101000000010100000001010000000101000000010100000001010000000101000000010)

■実行結果

21


保育園遅れる！