整数幂运算的二进制优化递归实现

整数幂运算

$2^n = n 个 2相乘$

普通递归实现

用幂的次数递归

$2^n = 2^{n-1}\cdot2$

如: $2^5 = 2^4 \cdot 2$

int power(int x,int n)
{
    if(!n) return 1;    // 递归的终止情况, n = 0 时返回 1
    return power(x, n-1)*x;
}

power(2,n);

二进制优化递归实现

幂的次数二分, 或者说用幂的次数的二进制位来递归
$$ 2^n = \begin{cases} (2 ^ {\lfloor n/2\rfloor} )^2 \cdot 2 \quad n 为奇数\\ (2 ^ {\lfloor n/2\rfloor} )^2 \quad \quad \space n 为偶数 \end{cases} $$
如:

$2^9$ 的二进制形式为 $2^{1001_2}$

第一次递归
十进制形式
$$2^9 = (2^4)^2 \cdot 2 \space \quad \quad $$
二进制形式
$$2^{1001}=(2^{100})^2 \cdot 2 \quad $$

第二次递归
$$2^4 = (2^2)^2 $$
$$2^{100} = (2^{10})^2 $$

第三次递归

$$2^2 = (2^1)^2$$
$$2^{10} = (2^1)^2$$

第四次递归
$$ 2^1 = (2^0)^2 \cdot 2\\ $$

代码实现

int power(int x,int n)
{
    if(!n) return 1;    // 递归的终止情况, n = 0 时返回 1

    if( n & 1)          // 判断 n 是否为奇数
        return pow(power(x, n >> 1), 2) * x;    // n 为奇数
    else
        return pow(power(x, n >> 1), 2);        // n 为偶数
}

power(2,n);

扩展阅读
多重背包问题的”二进制”优化