c++ - 谁能解释一下下面的代码片段？

Question

void dec_exp(Decimal *result, const Decimal *a, unsigned int b)
    {
        Decimal tmp, power = *a;
        dec_parse(result, "1");
        while (b)
        {
            if (b & 1)
            {
                tmp = *result;
                dec_mul(result, &tmp, &power);
            }
            if (b >>= 1)
            {
                tmp = power;
                dec_mul(&power, &tmp, &tmp);
            }
    }
}

其中Decimal是一个包含十进制值的结构体变量，它的长度和小数点所在的位置。

函数中传递的参数:a 是基值，b 是幂。 result 将存储计算后的值 a^b。

dec_parse(Decimal &x,string y) 会将 y 解析为十进制，并提取小数点位置等信息，修剪前导零和尾随零并进行转换字符串转换为 Decimal 结构变量。

dec_mul(Decimal result, Decimal &x, Decimal &y) 将 x 和 y 相乘，并将相乘后的值存储在 result 中。

我只想知道两个“if 条件”在 while 循环中如何工作，以及 while 循环何时终止以及代码片段的时间复杂度。

Answer 1

这是在 b 是非负整数的特殊情况下计算 (*a)b .

变量 result 初始化为 1(请注意，a⁰ 对于所有 a 都是 1)并且power 被初始化为a 的内容。每次循环时，如果 b 为奇数(第一个 if)，result 就会乘以 power。第二个 if 将 b 右移一位(即除以二)，如果它仍然是正数，则它与 power 平方。换句话说，power 包含逐渐变大的 (*a)²ⁿ 值。

这是一种计算 a^b 的相当高效且易于实现(但不是最优)的算法。最佳算法是 NP 困难的并且(可能)需要大量内存。该算法很容易编码并且需要最少的内存。

忽略多余的乘法，该算法对于 b=0 到 b=14 是最佳的。它在 a¹⁵ 中不是最优的。此算法计算为 a¹⁵ a*a²*a ⁴*a⁸，或六次乘法。最佳计算(调用 decimal 次数最少的计算)是 a³=a*a*a; a¹⁵=a³*((a^{3)2)2，或五次乘法。}

<小时/>

该算法的另一个名称是从右到左的二进制求幂。之所以这样称呼，是因为它从 b 的最右边的位(个位)开始，并逐渐作用于 b 的更高有效位。换句话说，它是从右到左工作的。从左到右的二进制求幂从 b 的最高有效位开始，并逐渐对 b 的较低有效位进行计算。在消除了多余的乘法 1 后，两种算法使用的乘法次数完全相同。

这不是“最佳”算法，其中最佳意味着“最少的乘法次数”。例如，从右到左和从左到右的二进制求幂算法将 x¹⁵ 和 x³¹ 计算为

• x¹⁵ = x*x²*x⁴*x⁸ = ((x^>2*x)²*x)²*x(分别从右到左和从左到右)
• x³¹ = x*x²*x⁴*x⁸*x¹⁶ = (((x²*x)²*x)²*x)² *x

但是由于 15=(4+1)*3、31=15*2+1=((4+1)*3)*2+1 和 31=7*4+3=(3*2+ 1)*4+3我们也可以写成:

• x¹⁵ = (x⁴*x)³
• x³¹ = ((x⁴*x)³)²*x
• x³¹ = (((x³)²*x)⁴)*x³

所有的乘法运算都比二进制求幂少一次。 (最终表达式需要缓存中间结果 x³ 以避免计算两次。)我不知道 x³¹ 的表达式是否是最佳的。即使对于较小的数字，找到最佳表达式也是极其困难的。您必须考虑表达 xⁿ 的所有不同方式，并记住常见的中间结果只需要计算一次。如上所述，这是 NP 困难的。在实践中，二进制求幂虽然不是最佳的，但已经足够了。