TarZの日記： バイナリアンには 2^n物差し！ 4
日記 by
TarZ
11cm + 5cmじゃだめなんでしょうか？
複数の長さを足してよいなら、この2^n物差しがとっても便利！
+-+-+---+-------+--
0 1 2 4 8 ...
たとえば 3 を測りたいなら、
3 = 2 + 1
5 を測りたいなら、
5 = 4 + 1
足す回数を増やすことで、大きい数にも対応します！
255 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
「でもお高いんでしょう？」
… … … …
と、ここまでネタを書いてオチをどうしようか考えていた時に思ったのだが、長さ 255 を測るなら 2^8(256) - 2^0(1) したほうが手っ取り早い。
任意の数に 2^n の数を加減算して到達する最小ステップを求める問題って、なんという名前だろう。
冗長２進数 (スコア:1)
0と1のほかに-1（1のバー）を導入して任意の数を表記（冗長２進数）しようと思うと二通り以上のやり方がある場合があります。で、数を表記するときに出来るだけ多くの桁で0になるようにする問題でしょうかね。
たしか、Hamming Weightってのが0でない桁の数だった気がします。間違ってたらすいません。
Re:冗長２進数 (スコア:2)
はい、おっしゃるように冗長2進数を導入することですっきり解決するようです。
tkobaさんが紹介されている形式が ~1を導入して 2進表現の2桁（情報量2ビット）毎に 00=0 , 01=+2^0 , 10=+2^1 , 11=0~1(-2^0) と表現できるので、情報量的にもこれが計算数最小ということになりそうですね。
冗長二進法における非隣接形式 (スコア:1)
広義の記数法 [wikipedia.org]参照。
Re:冗長二進法における非隣接形式 (スコア:2)
どうもありがとうございます。
ふむふむ、0 ～ 2^n-1 までの数を 2^x の加減算で表すときに必要な数は、最大で2進表現の桁数（n個）の半分+1 。たとえば n=4(15) までで一番加減算が多くなるのは 11 と 13 で、それぞれ
11 = (+)2^4 (-)2^2 (-)2^0
13 = (+)2^4 (-)2^2 (+)2^0
おおーなるほど、これは便利。