2001 年度「計算機基礎論３Ｂ」 2001-12-11

実習（の一例）

加減乗除の演算子は使わず、 ビットごとの論理演算子（と代入演算子）だけを用いて、 非負の数の足し算を行なう関数 int add(int x, int y); を書け。

ヒント： 二進のまま、筆算で足し算をするには、 次の (a) - (d) のようにするであろう。

    101       101       101       101
   +111      +111      +111      +111
  ------    ------    ------    ------
                0        00      1100

    (a)       (b)       (c)       (d)

次に二の桁。 0 + 1 = 1 であるがくり上がりがあったからそれも加えて 10 である。 0 を記入し、次の桁へのくり上がりがある、と記憶しておく。(c)

最後に四の桁。 1 + 1 = 10 にくり上がりの 1 を加えて 11 である。 これを記入する。(d)

これをプログラムにしてみよう。

• 整数型変数 x からその一の桁だけを取り出すには、 同じ型の変数 mask に 1 を代入しておいて x & mask とすればよい。
• 一桁の数 x と y を足した結果の一の桁は x ^ y で求められる。
• 一桁の数 x と y を足した際の二の桁へのくり上がりは x & y で求められる。

次に二の桁。 mask <<= 1 とすると、 mask は左に一ビットシフトされるので 2 となる。 今度は、x, y の二の桁だけでなく、 一の桁からのくり上がりも計算にいれなければならないので少し複雑になる。

こうやって計算してゆき、mask が最上位ビットに一つだけ 1 をもつ数のときの計算も済ませたとする。 次に mask <<= 1 とすると mask は 0 になる。 そうなったらループを抜けて終わるようにする。

この関数を試す main() では、 普通に + で足した結果と比較してみるのが一番よいだろう。 その際、rand() で発生させた乱数で実験する方法もある。

乱数の種を現在時刻で設定する方法

===============================================================================
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

main()
{
    int i;

    srand((unsigned int) time(NULL));

    for (i=0; i<20; i++) {
        printf("%d\n", rand());
    }
}
===============================================================================