自然な整数→ビット列

資料シート●各科目

ビット列
03
自然な整数→ビット列

△
● | ＞

http://www.infonet.co.jp/apt/March/syllabus/bookshelf/bit/03.html

点数

　ビット列に含まれているビットは、それぞれ点数を持っている。

・×はどこにあっても0点
・○はある場所によって点数が違う
　・最も右の端の○は1点
　・その左の○は2(=2×1)点
　・その左の○は4(=2×2)点
　・その左の○は8(=2×4)点
　...

　この点数は、そのビットがビット列の強さにどれだけ役立っているかを表わしている。
　ビット列に含まれる全部のビットの点数を合計したものを、そのビット列の点数という。

自然な整数＜ビット列

　ビット列(たとえば××××○○××)に対して、これに対応する自然な整数が分かる方法がある(これももちろんビット列を並べた表を上から数えれば分かるが)。
　これは以下のようにすればいい。
・ビット列の各桁のビットの点数を求めて、その下に書いていく(点数が0だったら省略していい)
・書き出した全部の点数を合計する

　二つの種類のものごとやことがらの間でそれぞれが対応している場合に、片方の種類のものに対してもう片方の種類の方の対応しているものを見つける(または作り出す)操作を変換という。

自然な整数＞ビット列

　自然な整数(たとえば12)に対して、これに対応するビット列が分かる方法がある(もちろんビット列を並べた表を上から数えれば分かるが)。
　こっちは逆の変換より少し手間がかかる。

・2^nの表の各桁の下に×を描いておく
・2^nの表を右から見ていって、12以下で最も大きい2^nを見つける。12に対しては8
・その下の×を○に描き直す
・12から8を引く。4ができる(12より小さい数を見つけて引いたから負にはならない)
・2^nの表を右から見ていって、4以下で最も大きい2^nを見つける。4に対しては4(そのもの)
・その下の×を○に描き直す
・4から4を引く。0ができる。これで完了

　この手順は必ず(しかもかなり早く)完了する。そして、いつの間にかもとの自然な整数(上では12)に対応するビット列(上では××××○○××)ができている。

△
● | ＞