【Ruby】【アルゴリズム】Rubyの補数とは。グレイコード。

　
Rubyにて、補数がよく分からなかったので整理。

printf "%b" , -0b110  #<= '..1010'

　
どうしてこの結果になるかというと、
110の2の補数は1010 だから。
　
110 のビットを反転して001→
1をたして010→
左側に無限の1を加えて..1010
　
そっか。

• 0b110 は0b110の2の補数をあらわす。

110 + x = 0 となるxをあらわしてる。
頭が混乱してた。

i & -i

これで最右の1を得られる。
　

11.times do |i|
	next if i == 0
	tmp = i^(i >> 1)  #<= グレイコード
	p "#{tmp.to_s(2)}"
end

グレイコードは書けたものの
これをどうやってハノイに活用すればいいのか
（動いた円盤は分かるけどどこに動くのか）
　

(1) 左側に数字１が現れないとき (００１，０１０，１００)
空いている棒(のひとつ)に移動する．
(2) 数字１が左隣にあるとき (０１１，１１０，１１１)
その１が表す下位からの位に対応する円盤のある位置に移動する．
(3) 数字１が０を１つ挟んで左側にあるとき， (１０１)
数字１が表す円盤のある位置以外の場所に移動する．

http://izumi-math.jp/F_Nakamura/hanoi_n/hanoi_n2.pdf

うーん、ちょっと分からない。

最右の1ビット位置を求める「ものすごい」コード

http://d.hatena.ne.jp/siokoshou/20090704#p1を参考に。

table = []
_hash = 0x03F566ED27179461
64.times do |i|
p (_hash >> 58).to_s(2)
	table[_hash >> 58] = i
	_hash <<= 1
end
p table

実行したらメモリが飛びました。
なぜだ？

■実行結果

"0"
"1"
"11"
"111"
"1111"
"11111"
"111111"
"1111110"
"11111101"
"111111010"
"1111110101"
"11111101010"

なるほど。Rubyは桁あふれの概念がないから
左シフトしてもただ桁が増えていくだけなんだ。。
Rubyでビット演算は（桁の概念がないだけに）難しそう。
　
概念的にはビットカウントテーブルを使うやり方と似てる。

とりあえず「ビット演算に慣れる」の目標は一旦完成でいいか。。