K3の住民

最近レア社のことをほとんど書いていない自称レア社好きがゲームやプログラミングについて色々書いていく。

【Cプログラミング】加算だけで表現する整数の計算

2019/07/21 除算の項の最後のプログラムに#include <stdio.h>を追加

皆さん、こんにちは。雪圀です。

今回はCプログラミングで「加算だけで表現する整数の計算」をやってみようと
思います。


正直に書きましょう。

しょーもないです。

なんかどっかで「プログラミングにおいて減算、乗算、除算はすべて加算で表現
されている」って聞いたような気がしたので、実際にプログラミングでやってみよう
と思いました。

とはいっても、加算だけじゃなくて、データのbit反転とかもしたりしてます。これ
がないとさすがに減算や負の乗算や除算が表現できませんでした。すいません。

減算

減算をする場合は、第二項を負の値に変換し、加算すればいいので、

(変数1) + -(変数2)

とすれば・・・はダメですね。なぜなら、-1を乗算してしまっているからです。
ではどうすればいいのか?

ここで使われるのが、bit反転です。

bit反転とは、二進数の値を真逆にすることです。つまり1は0、0は1に変わります。
たとえば23は

23 = 0b00010111

なので、これをbit反転すると、

0b11101000 = -24

となります。
しかし、bit反転だけでは-1の余分があります。この余分がある値を1の補数
いいます。
この値に1を加算し2の補数にすることで正の値を負の値に変換できます。

ではこれをプログラムで実現してみます。

#include <stdio.h>

int main(void)
{
	int num1, num2, cal;
	
	// 値の入力
	scanf("%d", &num1);
	scanf("%d", &num2);
	
	// 減算
	cal = num1 + ~num2 + 1;
	
	// 計算結果の出力
	printf("%d - %d = %d\n", num1, num2, cal);
	
	return 0;
}

乗算

皆さんは算数でかけ算を習うとき、おそらくこう習ったのではないでしょうか。

「2 × 3の場合、3個の2を足し合わせる」

つまり、乗算は加算を繰り返しているだけなのです。ここまで来たら懸命な人には
すぐにわかるでしょう。
そうです、ループ文を使います。

for(i=0; i < num2; i++) cal += num1;

forループにより、以上のような回数iがnum2回に達するまで加算を繰り返すことが
できるので、乗算を実現することができます。

ただし、正の乗算は実現できましたが、負の乗算は実現できていません。負の乗算
は以下のforループにより実現ができます。

for(i=0; i < (~num2 + 1); i++) cal += ~num1 + 1;

負の乗算も単純に回数iがnum2回になるまで繰り返せばいいのですが、num2は
負の値なので正の値に変換します。
ちなみにこのように書くことで、もう少し効率良く計算することもできます。

for(i=num2; i < 0; i++) cal += ~num1 + 1;

これは回数iが負の値のとき、0回になるまで繰り返すことで負の乗算を実現して
います。効率がいい理由は、num2を負の値から正の値に変換するというプロセスが
いらなくなるからです。

最終的には以下の形になります。

#include <stdio.h>

int main(void)
{
	int num1, num2
	int cal = 0;
	int i;
	
	/* 入力は省略 */
	
	// 正の乗算
	for(i=0; i < num2; i++) cal += num1;
	// 負の乗算
	for(i=num2; i < 0; i++) cal += ~num1 + 1;
	
	// 計算結果の出力
	printf("%d * %d = %d\n", num1, num2, cal);
	
	return 0;
}

計算結果の初期値は0なので、0を乗算した場合初期値のままになる、つまり0になる
ようにしております。

除算

正直これが一番時間かかりました

というのも、そもそも最初は乗算は加算だけでも実現できるという情報からこれを
思いついたので、乗算の理論はすでに頭の中で完成された状態で設計を始めたから
なんですけど。

そんな裏話はおいといて、今回の除算で思いついた理論は「計算回数を求める」
というものです。
なぜこうなるのかというと、x * y = zという式があったとして、yを求める形に変形
すると、

x * y = z
(x * y) / x = z / x
y = z / x

という形になります。zを求めるにはy回xを加算するので、yを求めるためにはzに
なるまでxを加算する回数もしくはzが0になるまでxを減算する回数を求める必要が
あります。つまり、除算を実現するには計算回数を求めればいいことになります。
なぜ「計算回数」とあいまいな表現をしているのかというと、計算回数の求め方は
加算していく方法と減算していく方法があるからです。
今回は加算だけでできるだけ効率良く表現したいので、加算していく方法を選んで
います。

さて、この方法だと、割り切れない場合はどう処理すればいいのか、という問題
があります。が、今回のプログラムではそれはあまり意識する必要がありません。
なぜかはあとで解説します。

最後に、正の値と負の値による計算方法の違いについてですが、正直ここはかなり
無理やりなものとなってしまいました。
これもプログラムの方で解説します。

いろいろ設計と試行錯誤をして作った除算は以下のようになりました。

if(num2 != 0) {									// 0除算防止
	if(num1 > 0) {								// num1が正の整数
		if(num2 > 0) {							// num2が正の整数
			for(i=num2; i <= num1; i += num2) cal++;
		} else {							// num2が負の整数
			for(i=num2; i >= (~num1 + 1); i += num2) cal += -1;
		}
	} else if(num1 < 0) {							// num1が負の整数
		if(num2 > 0) {							// num2が正の整数
			for(i=num2; i <= (~num1 + 1); i += num2) cal += -1;
		} else {							// num2が負の整数
			for(i=num2; i >= num1; i += num2) cal++;
		}
	}
}

はい、見ればわかると思いますが、sum1が正でsum2が正の場合、sum1が正でsum2
が負の場合・・・といった感じで、4通りすべての計算方法が異なったため、以上の
ような形となってしまいました。これでもまだ処理速度としてはマシなほうなんです
よね。
まぁ、乗算の場合加算を繰り返すだけだったので、それに比べて計算回数を求める
除算はやはり求め方が特殊で4分岐未満でやるのは無理があると思いました。

さて、割り切れない場合の処理ですが、僕が今回実現したいのは「小数点以下を
切り捨てする」という処理にしたかったのです。なぜならプログラム上、整数の
割り切れない計算はそう処理されるからです。
そこも懸念しましたが、範囲指定が必要だったというぐらいで、特に考える必要は
ありませんでした。
おそらく、プログラム上での除算も割り切れない場合は「小数点以下切り捨て」を
したほうが処理が楽だからそのようにしてるのでしょうね。

それと、一番冒頭の条件についてですが、これは0除算を防ぐ分岐です。もし仮に
0で割ろうとしていた場合に除算処理を飛ばすことができます。その場合、エラー
処理に行くのが一般的です。

最終的には以下の形になります。

#include <stdio.h>

int main(void)
{
	int num1, num2
	int cal = 0;
	int i;
	char flg = 0;
	
	/* 入力は省略 */
	
	// 除算
	if(num2 != 0) {									// 0除算防止
		if(num1 > 0) {								// num1が正の整数
			if(num2 > 0) {							// num2が正の整数
				for(i=num2; i <= num1; i += num2) cal++;
			} else {							// num2が負の整数
				for(i=num2; i >= (~num1 + 1); i += num2) cal += -1;
			}
		} else if(num1 < 0) {							// num1が負の整数
			if(num2 > 0) {							// num2が正の整数
				for(i=num2; i <= (~num1 + 1); i += num2) cal += -1;
			} else {							// num2が負の整数
				for(i=num2; i >= num1; i += num2) cal++;
			}
		}
	} else {									// 0除算
		flg = !flg;								// フラグの切り替え
	}
	
	// 計算結果の出力
	if(flg == 0) printf("%d / %d = %d\n", num1, num2, cal);
	else printf("ERROR!\n");
	
	return 0;
}

簡易電卓

以上の計算を利用して、簡易電卓を作ってみました。

ダウンロードページはこちら

詳しい仕様などは配布するファイルにあるreadme.txtをご覧ください。


以上です。

簡単にできると思っていましたが、除算で結構時間をかけましたねー。
しかもちょっと無理やりな計算方法になっちゃったし。一応これ以上効率化できない
か模索中です。

今回はこれくらいにしときます。