演習問題：掛け算のアルゴリズム（C言語）

掛け算を「*」「/」「%」演算子を使わずに実装するにはどうすればいいでしょうか？

掛け算の仕組みをアルゴリズムとして考える練習です。

掛け算とは
足し算式の掛け算（回答例１）
筆算の掛け算
筆算を２進数に置き換えて掛け算（回答例２）
まとめ

掛け算とは

63×42＝2646

この計算は63を42回足すことで求まります。小学校の九九の前後で教わる掛け算の概念のままですね。

足し算式の掛け算（回答例１）

九九のようにひたすら足し算します。

#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回もループして足し算をしているため、大きい掛け算になるほど時間がかかるようになってしまいます。

高速に計算できるのか筆算から考えてみましょう

筆算の掛け算

小学校で習う筆算では63ｘ2　と63ｘ40　の解を足し算して求めます。

これを１０進数のまま掛け算するには、４0と２に分けるときに割り算使うことになり、掛け算使わずに割り算で掛け算を実現するという変なかいとうになってしまうため。１０進数で考えるのはパスします。（それでもいい書いてほしいときはコメント欄に希望あり！って書き込みをお願いします）

ということで次は、２進数で考えてみると、0011 1111 x 0010 0010 という掛け算になります。

２進数　0011 1111 x 00100 0000  +  0011 1111 x 0000 0010

という計算になります。２進数の掛け算は１ビット左シフトで代用できるためコードは。

筆算を２進数に置き換えて掛け算（回答例２）

#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;
}

下の桁から１があれば掛け算（bitと同じだけ左シフト）をして足していき、最上位の桁になったら終了しています。