掛け算を「*」「/」「%」演算子を使わずに実装するにはどうすればいいでしょうか?
掛け算の仕組みをアルゴリズムとして考える練習です。
掛け算とは
63×42=2646
この計算は63を42回足すことで求まります。小学校の九九の前後で教わる掛け算の概念のままですね。
足し算式の掛け算(回答例1)
九九のようにひたすら足し算します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <stdio.h> int kakezan( int in1, int in2) { int ans = 0 , i; for (i = 0 ; i < in2; i++){ ans += in1; } return ans; } int main() { int a = 63; int b = 42; printf ( "test %d * %d = %d\n" ,a,b,kakezan(a,b)); printf ( "sample %d * %d = %d\n" ,a,b,a*b); return 0; } |
出力結果は
$main
test 63 * 42 = 2646
sample 63 * 42 = 2646
正しく答えが出ています。
でもこれだと、計算に時間がかかります。42回もループして足し算をしているため、大きい掛け算になるほど時間がかかるようになってしまいます。
高速に計算できるのか筆算から考えてみましょう
筆算の掛け算

小学校で習う筆算では63x2 と63x40 の解を足し算して求めます。
これを10進数のまま掛け算するには、40と2に分けるときに割り算使うことになり、掛け算使わずに割り算で掛け算を実現するという変なかいとうになってしまうため。10進数で考えるのはパスします。(それでもいい書いてほしいときはコメント欄に希望あり!って書き込みをお願いします)
ということで次は、2進数で考えてみると、0011 1111 x 0010 0010 という掛け算になります。
2進数 0011 1111 x 00100 0000 + 0011 1111 x 0000 0010
という計算になります。2進数の掛け算は1ビット左シフトで代用できるためコードは。
筆算を2進数に置き換えて掛け算(回答例2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <stdio.h> int kakezan( int in1, int in2) { int ans = 0 , s, t; for (s = 0; (1<<s) <= in2; s++){ if ( ( in2 & (1<<s) ) != 0) { ans += in1 << s; } } return ans; } int main() { int a = 63; int b = 42; printf ( "test %d * %d = %d\n" ,a,b,kakezan(a,b)); printf ( "sample %d * %d = %d\n" ,a,b,a*b); return 0; } |
下の桁から1があれば掛け算(bitと同じだけ左シフト)をして足していき、最上位の桁になったら終了しています。
まとめ
- ビットシフトと足し算で掛け算は作れる
- 左1ビットシフトで2倍と同じ
割り算に比べ掛け算は、思ったより簡単に終わりましたが、C言語の研修で行うbitシフトの演習にちょうど良さそうだなと思いました。
コメント