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

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

整数幂运算

2 n = n 个 2 相 乘 2^n = n 个 2相乘 2n=n个2相乘

普通递归实现

用幂的次数递归

2 n = 2 n − 1 ⋅ 2 2^n = 2^{n-1}\cdot2 2n=2n−1⋅2

如: 2 5 = 2 4 ⋅ 2 2^5 = 2^4 \cdot 2 25=24⋅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 = { ( 2 ⌊ n / 2 ⌋ ) 2 ⋅ 2 n 为 奇 数 ( 2 ⌊ n / 2 ⌋ ) 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} 2n={(2⌊n/2⌋)2⋅2n为奇数(2⌊n/2⌋)2 n为偶数​
如:

2 9 2^9 29 的二进制形式为 2 100 1 2 2^{1001_2} 210012​

第一次递归
2 9 = ( 2 4 ) 2 ⋅ 2   十 进 制 形 式 2 1001 = ( 2 100 ) 2 ⋅ 2 二 进 制 形 式 2^9 = (2^4)^2 \cdot 2 \space \quad \quad 十进制形式\\ 2^{1001}=(2^{100})^2 \cdot 2 \quad 二进制形式 29=(24)2⋅2 十进制形式21001=(2100)2⋅2二进制形式
第二次递归
2 4 = ( 2 2 ) 2 2 100 = ( 2 10 ) 2 2^4 = (2^2)^2\\ 2^{100} = (2^{10})^2 24=(22)22100=(210)2
第三次递归
2 2 = ( 2 1 ) 2 2 10 = ( 2 1 ) 2 2^2 = (2^1)^2\\ 2^{10} = (2^1)^2 22=(21)2210=(21)2
第四次递归
2 1 = ( 2 0 ) 2 ⋅ 2 2^1 = (2^0)^2 \cdot 2\\ 21=(20)2⋅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);
上一篇:Luogu3540 [POI2012]SQU-Squarks 题解


下一篇:[PHP] Compile an extension on Windows