掛け算を使わずに掛け算する

というわけで昨日の続き。まずはコードから紹介します。昨日の add() を使ってます。

int mul(int a, int b)
{
    int c = 0;
    while (b != 0)
    {
        if (b & 1)
            c = add(c, a);
        b >> = 1;
        a << = 1;
    }
    return c;
}

オーバーフローとか負数のことは考えていません。特にbを負にすると無限ループに陥るので、実用はしないでください。

計算の原理は簡単で、小学校の時に習う2桁以上の掛け算の筆算を、2進数でやっているだけなのです。だからこのアルゴリズム自体は小学生でも書き起こせます。実際、私はマシン語で(紆余曲折あったものの)こういうのを書いては「おー掛け算できた! 速くなった!」とか一喜一憂していたものです。ちなみに私が使っていたMSXはCPUはZ80だったので掛け算命令はありませんでした。

なおブースの乗算アルゴリズムとか、ついさっき知ったw