多倍長整数演算:繰り下がり

大学 C/C++ programing

とりあえずレポートできたしもうこのネタは終わりにしよう。早く自分の開発に戻らねば。このところバイトと大学に追われてしまっている..orz


RubyのBignumを読んでてなるほどと思ったこと。(たぶん他のどの実装も同じはず)
多倍長整数の減算をする場合は繰り下がりが起こる。

    ... u[1] u[0]
 -) ... v[1] v[0]
------------------
    ... w[1] w[0]

上の筆算では(ここでは仮に一桁8ビットで計算してると仮定する)

  1. u[0] >= v[0] なら w[0] = u[0]-v[0] で繰り下がりはなし
  2. u[0] < v[0] なら w[0] = 2^8 + u[0] - v[0] で 上の桁の計算の際は1を引く(繰り下がり)

ここの比較を条件分岐にしてしまうと非常に非効率。
んで、2の補数表現が使われてる場合はこれが非常にエレガントに処理できる。
一桁8ビットの場合
x >= 0 なら unsigned x = x
x < 0 なら unsigned x = 2^8 + x
となるので分岐が必要なく、見事に上の結果が得られる。
さらに素晴らしいのが、演算途中は1桁の2倍のバイト数の型を使うことの副作用。
(BDIGIT_DBL_SIGNED) num = u[0] - v[0]
この時繰り下がりが生じる(num<0)時はnumの上位ビットは全て1になる。
つまり上位ビットを取り出すとその値は-1。繰り下がりが生じなければ上位ビットを取り出した値は0。
よって、繰り下がりが生じようが生じまいが,num >> 8を次の桁の計算に加えるだけでよい。

2の補数表現ってなかなか面白いな。