Edited at

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


どういうこと?

気軽に計算機を使っている皆さん、その原理は説明できますか?数学においては、証明していない定理は使えません。プログラムにおいては、実装していない演算子は使えません。ということで、ビット演算のみで四則演算を実装します。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;
}


おわり!

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