コンピュータでの整数の計算

 コンピュータで扱われる数は基本的に2種類です。1つは整数型と言われるもの,もう1つは実数型と言われるものです。

 Tiny Basic で扱う数は1つの実数型の数で,明示的には整数型の数は扱いません。しかし, C を始めとして,本格的なプログラミング言語では必ず整数型の数も扱います。そして整数型と実数型については,コンピュータ一般についての常識の範囲のものと言えます。そこで,ここでは整数型の数とその計算について説明します。

符号無し整数

 コンピュータで数を扱う場合,その数を格納する仕方によってその数の型の分類がされます。

 例えば,8ビット整数と言うと,8ビットのメモリーに整数型の方法で格納される数という意味です。

 整数をメモリーに格納する仕方は単純です。 まず,正の整数または0のみを扱うことを考えましょう。

例として8ビットのメモリーに正の整数または0を格納するとします。その方法は簡単です。

8ビットメモリーは

               

8個の箱に0,1が入ると考えられます。これらを2進法で表す数と見ると,2=256の数を表すことが出来ます。最小の数0が

0 0 0 0 0 0 0 0

と格納され,最大の数255が

1 1 1 1 1 1 1 1

と格納されます。一般に a7,a6,a5,a4,a3,a2,a1,a0,を0または1とするとき,

a7 a6 a5 a4 a3 a2 a1 a0

は,

a7*27+a6*26+a5*25+a4*24+a3*23+a2*22+a1*21+a0

を表します。このような方法でメモリーに格納された数を

符号無し整数(unsigned integer)

と言います。8ビットの符号無し整数は0から255までの整数を表します。同様に

nビット符号無し整数は0から2-1までの整数

を表します。

符号無し整数での加減乗除

 符号無し整数の間での加減乗除は,基本的には筆算で行うような方法で可能です。 勿論このような計算は処理系で用意されますので,普通は意識する必要はありませんが,自前で多倍精度ルーチンを書く場合にはこのような知識は必須でしょう。


加法

a7 a6 a5 a4 a3 a2 a1 a0
b7 b6 b5 b4 b3 b2 b1 b0

は各桁同士を加え,繰り上がりは次の桁に送ります。

 この計算の場合,最上位の桁で桁上がりがあると,8ビットを飛び出してしまいます。この場合はその桁を無視することにします。つまり桁あふれの部分は無視をします。


減法

a7 a6 a5 a4 a3 a2 a1 a0
-
b7 b6 b5 b4 b3 b2 b1 b0

は下位桁から順次引き,引けない場合は上位の桁から借りてきます。

 この計算の場合,最上位の桁で 借りが必要になると,計算できません。(これは引く数の方が大きかったときです。)この場合の処理はエラーとしてしまう方法と,無理やり上位から借りてきて計算をしてしまう方法とが考えられます。

 どちらの処理をするかは,作る側の考えによるでしょう。しかし,加法の場合との整合性を考えると,常に上位から借りてきて計算をしてしまうのが自然でしょう。


乗法

a7 a6 a5 a4 a3 a2 a1 a0
×
b7 b6 b5 b4 b3 b2 b1 b0

これも筆算の場合と同様に計算することが出来ます。2進数の場合,各桁で掛ける数は0または1のみなので,計算は簡単です。

 具体的な例を挙げます。

                0 0 1 0 1 1 1 0        
              × 0 0 1 0 1 0 1 1        

                0 0 1 0 1 1 1 0        
              0 0 1 0 1 1 1 0          
            0 0 0 0 0 0 0 0            
          0 0 1 0 1 1 1 0              
        0 0 0 0 0 0 0 0                
      0 0 1 0 1 1 1 0                  
    0 0 0 0 0 0 0 0                    
  0 0 0 0 0 0 0 0                      

  0 0 0 0 1 1 1 1 0 1 1 1 0 1 0        

このように計算されます。この場合も8ビットを越える部分は無視します。


除法

a7 a6 a5 a4 a3 a2 a1 a0
÷
b7 b6 b5 b4 b3 b2 b1 b0

この場合も筆算と同様に計算することが出来ます。 2進数の場合,各桁で割る数として立つものは0または1のみなので,計算は簡単です。

 具体的な例を挙げます。

                  1 0 0 1              
        --- --- --- --- --- --- --- --- ---              
  1 0 1 ) 0 0 1 0 1 1 1 0              
              1 0 1                    
                    1 1 0              
                    1 0 1              
                    --- --- ---              
                        1              

このように計算されます。この場合は8ビットを越える部分はでて来ません。正確な商と余りが計算できます。


 以上のように符号無し整数での加減乗除は筆算で行われる方法によって可能です。そこで注意すべきこととして,結果がメモリーに納まらない場合は無視されると言うことです。

 この無視と言うことをよく考えると,実は今の場合8ビットなので,2=256を法にする整数の合同を考えることに対応しています。

 全ての整数は256を法にして,0~255のいずれかの数と合同です。そして256を法にして加減乗は普通に計算できました。このことに注意すると,上の加減乗の計算は,普通に計算をして,256を法にして合同になる0~255の数を取ることになっています。

 このことは一般にnビット整数でも全く同様です。即ち,

nビット符号無し整数での加減乗

  • 全ての整数は2を法にして,0~2-1の整数に合同になる。
  • 加減乗の結果は普通に整数計算を行う。
  • その結果と2を法にして合同になる0~2-1の整数を取ったものが最終結果。

となります。

 この事実は,特に取り立てて言うことの程ではない事実と感じるかもしれません。確かに,符号無し整数のみを扱っている場合はその通りでしょう。しかし,負の整数を含めて計算を行うことを考える場合,上の事実が重要なヒントになります。

符号付整数

 実際の数の計算では,負の数を扱うのが普通です。そこで次に負の数まで考えた整数の格納法と計算について説明します。このように負の数まで考えた整数を符号付整数(signed integer)と言います。

 負の数を扱う場合,符号を付けて表せば良いと考えるのは自然です。実際,先頭のビットを符号を表すとして,残りのビットで絶対値を表す方法もあります。しかし,一般に整数を表す方法としてはこれではなく,2の補数表示を使うのが普通です。以下にこの方法を説明します。

 

2の補数表示による整数

例として8ビットのメモリーに(正負の)整数を格納するとします。

 8ビットメモリーは,2=256の数を表すことが出来ます が,2の補数表示では,このうち半分を0または正の整数,残り半分を負の整数として表します。ですから,

0または正の整数は,0から127まで表すことが出来ます。また負の数は-1から-128まで表すことができます。即ち,

8ビットの2の補数表示による符号付整数は,-128から127までの数を表す

ことになります。一般に,

nビットの2の補数表示による符号付整数は,-2n-1から2n-1-1までの数を表す

ことになります。


 実際に数をメモリーに格納する方法をは次の通りです。

  • 0から127までの数は符号無し整数と同じ方法でメモリーに格納する。
  • -128から-1までの数は256を加えて,128から255までの数にして,それを符号無し整数と同じ方法でメモリーに格納する。

例えば -34は 256-34=222 として格納します。34からこの222を得る良く説明される方法として,34の整数表現の各ビットを反転し,それに1を加える方法があります。34は

0 0 1 0 0 0 1 0

と格納されますから,それを各ビット反転させると,

0 0 1

が得られます。これに1を加えたもの

1 1 0 1 1 1 1 0

が222で求める補数表示です。

 実際,反転させたものと元の数を加えると,255になりますから,それに1を加えたものが256になり,上の規則で決めたものと同じになります。


一般にnビットの2の補数表示による負の整数の格納の仕方も全く同様です。即ち,

-2n-1から-1までの数は2を加えて,2n-1から2-1までの数にして,
それを符号無し整数と同じ方法でメモリーに格納する。

この規則で,正整数から,それに負符号を付けたものに変換する方法は,

各ビットを反転(1は0に,0は1に)したものに1を加える

ことで得られます。

 

2の補数表示とは?
  • 0から127までの数は符号無し整数と同じ方法でメモリーに格納する。
  • -128から-1までの数は256を加えて,128から255までの数にして,それを符号無し整数と同じ方法でメモリーに格納する。

という表示規則は一見人為的に思われますが,整数の合同の理論の立場からすると,極めて自然なものです。

 実際,256を法とした合同関係では,256を加えても同じものと見做されます。そこで-128から-1までの数は256を法にした合同関係で8ビット整数として表されるものとしたのが上の規則です。

 この,256を法とした合同関係を使って定義した2の補数表示は次のような性質を持っています。


 1.負の数は最高位ビットが1である。

 2.正の数から負の数への変換が,ビット反転+1で実行される。

 3.加減乗の計算は,符号無し整数と全く同じ方法で行われる。

 4.範囲外の結果になる計算では,mod 2 での結果しか分からない。
 


証明

1.負の数は上の決め方から,128から255までの数ですから,10000000(2進数表示)=128以上で最高位のビットは1です。

2.aを正の整数≦127とし,そのビット反転した数を a' とします。このとき,

a+a'=11111111(2進数表示)=255=28 - 1

が成立します。従って a' + 1 = 28 - a であり,a' + 1が -a の補数表示になります。

3.a を整数として,正の場合には a'=a とします,負の場合には規則に従って符号無し整数に変換したものを a' とします。b についても同様に b' を定義します。このとき,a,b の正負に係らず

a ≡ a' (mod 256) b ≡ b' (mod 256)

が成立します。一方

a + b ≡ a' + b' (mod 256)

a - b ≡ a' - b' (mod 256)

a * b ≡ a' * b' (mod 256)

が成立しますから,左辺の結果が8ビット整数の範囲にあれば,右辺の結果の補数表示として得られます。

4.結果が範囲外になる計算の場合は,一見おかしな結果が得られます。例えば,今の場合(8ビット),128 は -128 を表しますから, 127+1 = -128 という結果が出ます。この場合は正確には

127+1 ≡ -128 (mod 256)

と解釈するべきでしょう。このように結果が格納の範囲外になる場合は当然ですが,正しい結果にはなりません。


上の性質のうち,3は大変好都合な性質です。

 これは例えば次のように計算が出来ることを意味しています。

-13×7

の計算をするとします。普通であれば,13×7=91 を計算して,符号を考慮して,

-13×7 = -91

を求めます。しかし,実は上の方法を考慮すると次のようにして計算出来ることが分かります。即ち,

-13 は元々2の補数表示で(符号無し整数の仕方で)243 としてメモリに格納されています。ですから,符号のことを考えないで,そのまま計算すると243×7=1701ですが,8ビット計算では桁あふれは無視しますから,1701 ≡ 165 mod 256 より,

-13×7 = 165 (8ビット整数での結果)

です。ここで,165 は2の補数表示では-91 です!つまり,計算では符号のことは一切考えずに符号なし整数として計算し,結果を表示するときだけ2の補数表示にすれば良いわけです。


 これらのことは加法や減法についても一般的に成立します。特に減法は符号を反転させて加えることで可能ですから,符号付き整数での加減乗の計算は,符号無し整数での加法,乗法,そして,符号の反転で計算可能です。

 Tiny Basic では整数型の数は使えませんが,整数型の数の雰囲気を知るためのプログラムを作りました。integer.tbt です。お試しください。

まとめ

 2の補数表示の性質は2を法とする整数の合同を使って理解するのが最適です。このように

計算機の内部での処理と初等整数論とは意外なところで関連している

ものです。整数の合同について馴染みのない人は是非整数の合同の項を読むことを勧めます。