【Ruby】【アルゴリズム】ビットカウント。最下位の1を倒していくVer。ループしないVer。

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

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

最下位の1を倒していく

def numofbits3 bits
	num = 0
	while bits != 0 do
		num += 1 if (bits & (bits-1))
		bits = bits & (bits-1)
	end
	num
end
p numofbits3(0b100000000000000000000000000000000000000000001)

■実行結果

2

　
なるほど。
「bits & (bits-1)」 は最下位の1をOFFにする働きがある。
いわれてみたら確かに。

ループを使わないVer

ビットを数える最適化されたアルゴリズム。
int numofbits5(long bits)
{
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

　
この数値は何を意味してるんだろう？

p 0x55555555.to_s(2)
p 0x33333333.to_s(2)
p 0x0f0f0f0f.to_s(2)
p 0x00ff00ff.to_s(2)
p 0x0000ffff.to_s(2)

　
■実行結果（整形しています）

"101_0101_0101_0101_0101_0101_0101_0101"
"11_0011_0011_0011_0011_0011_0011_0011"
"1111_0000_1111_0000_1111_0000_1111"
"1111_1111_0000_0000_1111_1111"
"1111_1111_1111_1111"

ふむ。。
　
以下のサイトを参考に理解しました。
http://www.st.rim.or.jp/~phinloda/cqa/cqa15.html#Q3http://tak5219.seesaa.net/article/7042181.html

なるほど。。
これは32ビットが上限だけど、

たとえば64ビットまで計算可能にするならばこうなる↓
もちろん左シフトで32ビットづつ減らしていってloopすることはできるけど。

target =Array.new(26,0)
target += Array.new(36,1)
value = target.shuffle!.join("")
bits = value.to_i(2)
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >>16 & 0x0000ffff0000ffff);
    bits = (bits & 0x00000000ffffffff) + (bits >>32 & 0x00000000ffffffff);
p bits

■実行結果

36

徐々に寄せるのか。。すごいな。