2進法への信奉 (Courseraの "From Nand to Tetris" Week2前半のおさらい)

今日の料理

砂肝のアヒージョ。

概要

Courseraでは、2進法で如何に計算するかということを説明していた。今回は、10進法を混じえながら、負の整数おび正の整数を如何に足すのか、について説明する。

n進法とは何か

まず最初に、身近な10進法について考えてみよう。9999以下の任意の正の整数をmとし、10進法を式で表わした場合、下のように表わすことができる。以下に現れる各nは10未満の正の整数だ。

この式を見るとわかるように、10進法を表現したい場合、下のような数式に直すことが可能であることがわかる。

この式自体はなんでもないというか、「当たり前のことじゃないか」と思われるかもしれない。しかし、この当たり前のことというのは、2進法の表現にも同様に使える。上と同様に、各nを2未満、0か1で表現する場合、15未満の任意の正の整数を表現したい場合には、次のように書くことができる。

2進法の表記はこういうことになる。ちなみに、この辺りをOCamlで書いた場合、下のようなコードとなる(汚ないコードで申しわけない):

let max_binary_list n =
  let rec generate_binary_list n m sum xs =
    if sum > n then xs
    else generate_binary_list n (m * 2) (m + sum) (m :: xs) in
  generate_binary_list n 2 1 [1]

let binary_flag_list n =
  let rec generate_flag_list n xs ys =
    match xs with
      [] -> ys
    | x :: next_xs ->
       let is_flag = n >= x in
       let next_n  = if is_flag then n - x   else n in
       let next_ys = if is_flag then ys @ [1] else ys @ [0] in
       generate_flag_list next_n next_xs next_ys
  in
  generate_flag_list n (max_binary_list n) []

これで作成したリストを元に戻すためには、次のようなコードを書けばよい。

let reverse_list zs =
  List.fold_left (fun list x -> x :: list) [] zs

let rec sum_binary n sum ys =
  match ys with
    [] -> sum
  | y :: yys ->
     sum_binary (n * 2) (if y == 1 then sum + n else sum) yys

let digit_of_binary_list_ignore xs =
  sum_binary 1 0 (reverse_list xs)

負の整数の2進法的表記

とりあえず、正の整数を2進法にするロジックはわかったわけだけれども、これは少々不満が残る。なぜなら、ある程度実用性を目指すとするならば、負の整数も表現する必要があるだろう。

そこで、一番最初のビットを「負か正か」の符号として当てはめることを考える。素朴に考えてしまえば、次のようになる。

001 ->  1
010 ->  2
011 ->  3
101 -> -1
110 -> -2
111 -> -3

しかし、このような単純な方法はどうも失敗のようだ。というのも、上の表ではわざと省いたが、「0」の時のパターンが「000」と「100」と二つになってしまうからだ。これでは、負の0と正の0で分裂してしまってよろしくない。そこで、今度は次のような符号化をしてみることを考える。

000 -> 0
001 -> 1
010 -> 2
011 -> 3
100 -> -4
101 -> -3
110 -> -2
111 -> -1

つまり、正の整数で表現される部分(上の場合ならば下2桁)から、負の符号がついているときだけ、そのbitが表現できる正の整数 + 1を引くようにするといい。これによって、0のゆらぎは無くなって、一つにまとめることができる。

確かに、0のゆらぎはなくなったからいいのだけれども、しかし、ぱっと見たところ、話を複雑にしているようにしか見えないだろう。しかし、このようにすると足し算が上手くいくというメリットがある。

足し算が上手くいく?どういうこどかといえば、次のように考えればいいらしい。

上の符号付き2進法は、それを愚直に2進法に直した場合、次のようになる:

000 -> 0
001 -> 1
010 -> 2
011 -> 3
100 -> -4 -> 4
101 -> -3 -> 5
110 -> -2 -> 6
111 -> -1 -> 7

ここで、2進法を利用して、「2 - 1」を計算することを考える。「2 - 1」は、つまるところ「2 + (-1)」である。上の場合ならば「010 + 111」となる。これを愚直に計算すれば、「1001」となる。いま利用しているbit数は2 + 1なので、「1000」は桁あふれとなって、切り捨てられる。すると、残るのは「001」となって、上の表だと1となる。

このような計算が上手くいくのは、これが8の周期性を持っていることと関係しているらしい。さきほどの「2 + (-1)」は、愚直な2進法で表す場合、「2 + 7」となる。これは「1 (mod 8)」となる。このとき、1番目にあたる数字というのが1というのが保証されている。従って、この計算は数学的に上手くいくことが保証されている。

もちろん、これが常に上手くいくとは限らない。この場合、ビット数が一緒であることがわかっていた。もし違う場合、ヘンテコなことになってしまう。

たとえば、4bitと8bitの場合、負の表現方法が違うのでずれてしまう。この二つを足しあわせる場合、工夫が必要になるのだけれども、今回の場合は、これは考慮せずに決めうちにすることにする。

擬似的なビット計算

さて、ここで愚直にビット計算を実装すると、桁の繰りあがりといったような半加算器であったり、全加算器といったような仕組みを導入する必要が出てくる。従って、今回は先ほど説明した、「2 + (-1)」を「2 + 7」にした上で、ビットの周期性を利用するという方法を使う。

まず、2進法表記にするための関数を定義する:

let binary_flag_list_with_bit n bit =
  let bit_size = (int_of_float (2. ** (float_of_int bit))) in
  let use_binary_list = max_binary_list bit_size in
  let if_minus_fix    = if n < 0 then (List.hd use_binary_list) * 2 + n else n in
  generate_flag_list if_minus_fix use_binary_list []

このあと、それ自体が負の整数かどうかを考慮せず、ただ正の整数として、10進法に直す関数を定義する:

let digit_of_binary_list_ignore xs = sum_binary 1 0 (reverse_list xs)

これを利用して、負の整数を正の整数に対応させる関数を定義する:

let digit_to_digit n bit =
  if n < 0 then
    digit_of_binary_list_ignore (binary_flag_list_with_bit n bit)
  else
    n

最後に、負の2進法を負の10進法として直す関数を定義する:

let digit_of_binary_list_with_minus xs =
  let first_number =
    if (List.hd xs) == 0 then 0 else
      - (int_of_float (2. ** ((float_of_int (List.length xs)) -. 1.)))
  in
  sum_binary 1 first_number (reverse_list (List.tl xs))

これを組みあわせると、次のようになる:

let setting_bit = 4
let d_t_d a = digit_to_digit a setting_bit
let bit_adder a b =
  let bit_mod x =
    x mod (int_of_float
             (2. ** ((float_of_int setting_bit) +. 1.)))
  in
 digit_of_binary_list_with_minus (
      binary_flag_list_with_bit (bit_mod ((d_t_d a) + (d_t_d b))) setting_bit)

使ってみる

# bit_adder 10 (-11);;
- : int = -1
# bit_adder (-11) (-3);;
- : int = -14
# bit_adder 12 (-3);;
- : int = 9

まとめ

今回、計算機についての本当に基礎的な部分について復習してみた。聞いてみると「なるほど!」と思うし、たぶん工学系の学生にとっては、あたりまえの事実であるような気がするけれども、しかしそういう出自ではない自分にとっては、とても興味深く、それ故に以前より計算機というのが身近に感じられるようになって、とてもうれしかった。

まとまってないほうのソース

• gist