四則演算を使わずに四則演算をする

どういうこと？

気軽に計算機を使っている皆さん、その原理は説明できますか？数学においては、証明していない定理は使えません。プログラムにおいては、実装していない演算子は使えません。ということで、ビット演算のみで四則演算を実装します。OSはWindows10、コンパイラはGCC8.2.0を使用しています。

※はじめは算術演算子以外はC++の演算子をそのまま使っていましたが、それらも全て自力で実装することにしました。使うのは代入演算子とビット演算子のみです。

まず、比較演算子==と!=の実装からやりましょう。他の比較演算子は加算と減算を終えた後で。

a == b

$a$と$b$のXORが$0$になるとき、$a==b$が成り立ちます。そのため、以下のように書けます。

eql.cpp

bool eql(int a, int b) {
    if(a ^ b) return false;
    return true;
}

a != b

逆に、$a$と$b$のXORが0でなければ、$a$ != $b$となります。

neq.cpp

bool neq(int a, int b) {
    if(a ^ b) return true;
    return false;
}

加算(a+b)

単純に、繰り上がらない部分$s$と繰り上がりの部分$t$を考えてみましょう。
繰り上がらない部分$s$は、$a$と$b$のXORで求めることが出来ます。
また、繰り上がりが発生するのは$a$と$b$の2進数における各桁が互いに1であるときです。そのため、繰り上がりを表すビット列$t$は、$a$と$b$のANDを1ビット左にシフトしたものとして表されます。
$s$と$t$を求めたら、$s+t$をする必要があります。そこで、再帰を用いて以下のように書けます。

add.cpp

int add(int a, int b) {
    if(eql(b, 0)) return a;
    return add(a ^ b, (a & b) << 1);
}

もちろん、ループ処理を使っても良いです。

add2.cpp

int add2(int a, int b) {
    int t;
    while(neq(b, 0)) {
        t = (a & b) << 1;
        a ^= b;
        b = t;
    }
    return a;
}

減算(a-b)

基本的な考え方として、よく補数を用います。補数とは、その数に加えると、ある一定の値になるような数のことです。つまり、10に対する6の補数は4、5に対する3の補数は2といった数になります。補数の求め方は簡単で、各ビットを反転させて1を足せば求められます。
減算は、$a$と$b$の補数を加算して上位1桁を無視することで実装できます。例えば7-4は、10に対する4の補数が6であるため、7+6=13、上位1桁を無視して3と求められます。
そのため、以下のように書けます。

sub.cpp

int sub(int a, int b) {
    int comp = add(~b, 1);
    return add(a, comp);
}

GCCでは負の値を補数で扱います。また、int型を4バイトとしています。そのため、bの補数は$2^{32} = 4,294,967,296$に対しての補数となります。なので、答えが正のときはオーバーフローが発生し、あふれた桁が無視されて正しい答えが得られます。また、負の値が補数で扱われていることから、以下のような書き方でも動作します。

add(a, -b);

さらに、加算のときと同じように、繰り下がらない部分$s$と繰り下がりの部分$t$を考えると、$s$は加算と同様にXORを取れば求められます。一方$t$は、$a$のビットが0、$b$のビットが1のときのみ、繰り下がりが発生します。なので、$t$の論理式は、$t=\bar{a}・b$となります。このことから、以下のようにも書けます。

sub2.cpp

int sub2(int a, int b) {
    if(eql(b, 0)) return a;
    return sub2(a ^ b, (~a & b) << 1);
}

a > b

さて、加算と減算が実装出来ました。この後の乗算と除算を行うために必要な演算子を準備しましょう。
$a>b$が成り立つとき、$a-b>0$が成り立ちます。ここで、GCCでのint型が4バイトであることから、int型の値は内部では$0〜2^{32}$であることが分かります。また、実際に人間がint型の値に代入できる数の範囲が$-2^{31}〜2^{31}$であるので、$0〜2^{31}$が正の数、$2^{31}〜2^{32}$が負の数(の補数表現)であると考えられます。よって、32ビット目が0ならば正、1ならば負と分かります。このことから、以下のように書けます。

gt.cpp

bool gt(int a, int b) {
    if(eql(a, b)) return false;
    int c = sub(a, b);
    c >>= 31;
    if(eql(c & 1, 0)) return true;
    return false;
}

a ≧ b

上のコードは、

if(eql(a, b)) return false;

とすることで、$a==b$となるパターンを排除しています。そのため、この部分を消去すれば$a≧b$を実装出来ます。

gte.cpp

bool gte(int a, int b) {
    int c = sub(a, b);
    c >>= 31;
    if(eql(c & 1, 0)) return true;
    return false;
}

a < b

$a<b$は、$a≧b$の否定です。もちろん、!gte(a, b)とするのではなく、32ビット目を確認しても良いです。

lt.cpp

bool lt(int a, int b) {
    int c = sub(a, b);
    c >>= 31;
    if(eql(c & 1, 0)) return false;
    return true;
}

a ≦ b

これは、$a>b$の否定です。

lte.cpp

bool lte(int a, int b) {
    if(eql(a, b)) return true;
    int c = sub(a, b);
    c >>= 31;
    if(eql(c & 1, 0)) return false;
    return true;
}

三項演算子

続いて、三項演算子を作ります。実装は単純です。

ter.cpp

int ter(bool cond, int a, int b) {
    if(cond) return a;
    return b;
}

乗算(a×b)

乗算は、人間が行う筆算と同様に、$b$の各ビットと$a$のANDを1ビットずつシフトして加算することで得られます。そのため以下のように書けます。

mul.cpp

int mul(int a, int b) {
    if(lt(a, 0)) return sub(0, mul(-a, b));
    if(lt(b, 0)) return sub(0, mul(a, -b));
    int result = 0;
    while(neq(b, 0)) {
        result = add(result, ter(eql(b & 1, 0), 0, a));
        b >>= 1;
        a <<= 1;
    }
    return result;
}

除算(a/b)

除算も、人間が行う筆算と同様に考えられます。なお、double型やfloat型ではビット演算が行えないため、商と余りを計算することとします。まず、商の計算です。$b$を$a$以下の範囲で左にシフトしていきます。そのとき、その位での商$c$も同様に左にシフトします。bを左にシフト出来なくなったところで、商$q$に$c$を足して$c$を1に初期化し、$b$を右に1ビットシフトします。$a$から$b$を引いた数を$a$とし、$b$を元々の$b$の値に初期化します。この処理を繰り返すことで除算を実装します。

quo.cpp

int quo(int a, int b) {
    if(eql(b, 0)) throw "Divide by zero";
    int original_b = b;
    int c = 1;
    int q = 0;
    while(gte(a, b)) {
        b <<= 1;
        if(gte(a, b)) c <<= 1;
        else {
            q = add(q, c);
            c = 1;
            b >>= 1;
            a = sub(a, b);
            b = original_b;
        }
    }
    return q;
}

ついでに剰余(a%b)

商の計算をしたので剰余計算もやりましょう。剰余$R$は、商を$Q$としたとき、$a=Q×b+R$が成り立つことから、$R=a-Q×b$として求められます。よって以下のように書けます。

rem.cpp

int rem(int a, int b) {
    return sub(a, mul(b, quo(a, b)));
}

おまけで累乗(a**b)

Pythonだと**演算子、C++だとstd::pow()で実装されてます。これもビット演算を用いて実装出来ます。

pow.cpp

int pow(int a, int b) {
    int result = 1;
    while(gte(b, 1)) {
        if(eql(b & 1, 1)) result = mul(result, a);
        a = mul(a, a);
        b >>= 1;
    }
    return result;
}

ただ、これは$b<1$のとき上手く動作しません。整数値しか扱っていないからです。よく書かれる累乗の実装はこんな感じです。

pow2.cpp

double pow(double a, int b) {
    if(b < 0) return pow(1 / a, -b);
    double result = 1.0;
    while(b >= 1) {
        if(b & 1 == 1) result *= a;
        a *= a;
        b >>= 1;
    }
    return result;
}

おわり！

自分で実装した演算子で演算子を実装するのは気持ちがいい！！！！！！！！