原理与快速幂相似，利用二进制将两个数的乘法运算转化为加法运算。具体代码如下:

int mul(int a,int b)
{
    int ans=0;
    while(b)
    {
        if(b&1)
            ans+=a;
        a+=a;
        b>>=1;
    }
    return ans;
}

加上取模的话是这样:

int mul(int a,int b,int p)
{
    int ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}

  快速乘其实是利用了二进制与乘法分配律。以 2 x 7 为例，因为 7(10) = 111(2) = 100(2)+ 010(2) + 001(2) = 4(10)+2(10)+1(10)，也就是 2 x 7 = 2 x ( 4 + 2 + 1 ) = 8 + 4 + 2，从而将乘法转化为加法(对于计算机而言，算加法要比算乘法快得多)

  我们再将快速幂与快速乘对比一下: 快速幂:

int fpow(int a,int b)
{    
    int ans=1;
    while(b)
    {
        if(b&1)
            ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}

快速乘:

int mul(int a,int b)
{
    int ans=0;
    while(b)
    {
        if(b&1)
            ans+=a;
        a+=a;
        b>>=1;
    }
    return ans;
}

可以发现，两者之间的差别只有加号与乘号的差别。这是因为，乘法就是若干次加法，而求幂就是若干次乘法。