読者です 読者をやめる 読者になる 読者になる

せかいや

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

【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) 左側に数字1が現れないとき (001,010,100)
空いている棒(のひとつ)に移動する.
(2) 数字1が左隣にあるとき (011,110,111)
その1が表す下位からの位に対応する円盤のある位置に移動する.
(3) 数字1が0を1つ挟んで左側にあるとき, (101)
数字1が表す円盤のある位置以外の場所に移動する.

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でビット演算は(桁の概念がないだけに)難しそう。
 
概念的にはビットカウントテーブルを使うやり方と似てる。

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