c - 当a，b，c在c中约为(x)e + 18时计算(a * b)％c

当a，b，c的阶数为10^18时，我发现这两个代码要计算（a*b）%c，但无法得到它们是如何工作的。有人能逐行解释这些函数是如何工作的吗

long long int mult(long long int x, long long int y, long long int mod)
{
    x = x % mod;
    y = y % mod;
    long long int z = 0;
    for (1; x; x >>= 1){
            if(x & 1)
            if((z =z+ y) >= mod)
               z = z- mod;
            if((y = 2 * y) >= mod)
           y =y- mod;
     }
     return z;
}

和

long long multiple(long long a, long long b, long long c) // a * b % c
{
        if (b == 0)
           return 0;

        long long ret = multiple(a, b >> 1, c);
        ret = (ret + ret) % c;
        if (b & 1)
             ret = (ret + a) % c;
        return ret;
}

我在解决在线比赛中使用过这些功能，我发现第一个功能比后者好/快得多，但为什么？

最佳答案

位移位将乘法运算转换为（条件）加法每次循环（第1个方法）或递归调用（第2个方法）时，代码都会查看其中一个操作数的至少一个有效位：如果已设置，则会将另一个操作数添加到运行总数中然后将第一个操作数右移（除以2），并将另一个操作数加倍（必要时使用模或减法）。
例如，如果数字是5和7，则5==101（二进制），因此：

x      y      z
--     ---    ---
101    7      7   (bottom bit set, add 7 to z)
10     14         ( x = x >> 1 ; y = y * 2 )
10     14     7   (bottom bit not set, don't add)
1      28     7   ( x = x >> 1 ; y = y * 2 )
1      28     35  (bottom bit set, add 28 to z)
0                 ( x = x >> 1 ; x is zero so stop)

关于c - 当a，b，c在c中约为(x)e + 18时计算(a * b)％c，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21110897/