c - 在计算 (a*b)%c 时，a、b、c 的顺序为 (x) e+18 in c

Question

我找到了这两个代码来计算 (a*b)%c，当 a、b、c 的顺序为 10^18 时，但无法理解它们是如何工作的任何人都可以逐行向我解释这些函数是如何工作的

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

我已经在解决在线竞赛中使用了这些函数，并且我发现第一个函数比后者更好/更快，但为什么呢？

Answer 1

移位将乘法运算转换为(条件)加法。每次循环(第一种方法)或递归调用(第二种方法)时，代码都会查看其中一个操作数的最低有效位:如果已设置，则将另一个操作数添加到运行总数中。然后它将第一个操作数右移(除以二)并将另一个操作数加倍(必要时使用模数或减法)。

例如，如果数字是 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)