ビット列の和

資料シート●各科目

ビット列
01
ビット列の和

△
＜ | ＞

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

　ビット列にも足し合わせが決められている(▽図)。ビット列の足し合わせは数とよく似ている。

　いくつかの(同じ長さの)ビット列がある場合、それぞれの桁ごとに、縦に並んだビットのうちの○の個数を調べる。
　そして、それが0個なら×、1個なら○がその桁の和になる(×は0、○は1だと思って見ると納得できるだろう)。そして、それらを列にしたものをビット列の和と言う。

例

　×××○××××
＋×××××××○
＝×××○×××○

　ただし、(その桁のうちで)見つけた○の個数が2個になったら、それまでに数えた個数は忘れて0個に戻さなければならない。つまり、○は2個になると互いに打ち消し合って消えてしまう。これを(正の)対消滅(exclusion)という([X Files]にそんな寄生虫の出てくるエピソードがあったよね)。
　対消滅が起ったら、そのたびに、その左隣りの桁に○を一つずつ書き足さなくてはならない。これを繰り上がり(carry)という。

例

　　○○　　　○　
　××○○×××○
＋×××○×××○
＝×○××××○×
　　　！！　　　！

　左の方の桁の和を求める時は、右の桁からの繰り上がりで追加された○の個数も合わせて数える。繰上りを考えなければならないので、ビット列の足し合わせは数の場合と同じように右の桁から左の桁に向かって順に進めていかなければならない。

例

　　○○　　　○　
　××○○×××○
＋××○○×××○
＝×○○×××○×
　　　！　　　　　

　以上をまとめると▽表のようになる。それぞれの桁での和と繰上りはその桁にある○の個数で決まっている。

○の個数	例	桁の和	繰上り
0	× ＋）×	×	×
1	×　　　　○ ＋）○　　＋）×	○	×
2	○ ＋）○	×	○
3	○ 　　○ ＋）○	○	○
...

　ただし、ビット列は長さが決まっているから、左端の桁で対消滅があった場合には、その繰り上がりを持っていける先はない。つまり、左端の桁についてだけは、繰り上がりはしない。

例

　××××××××
＋××××××××
＝××××××××

　○×××××××
＋○×××××××
＝××××××××

細かすぎる注釈

　数の表記法の一つに、2進表記がある。すぐ気がついたかもしれないが、ビット列の和は、数の2進表記での和とよく似ている。しかし、左端の繰上りの決め方はちょっと違っている。数の2進表記では桁の長さが自由に延ばせるが、ビット列ではいつも同じ桁の長さのものしか扱わないので、こんな違いが現われる。

　ビット列は、自然な整数を表現する名前として使われている。特に、一括2進化法を使って自然な整数にビット列を割り振ると、ビット列の足し算をするとそれによって数の方の足し算もできてしまうというたいへん役に立つ特性が得られる。現代のコンピュータは、この性質を利用して数の計算を行なっている。
　このように、ある実体についての操作と、記号での操作とが、実体から記号への変換と記号から実体への変換とによってそのまま対応している状態を、実体と記号との可換の4角形という。

△
＜ | ●