整数幂运算的二进制优化递归实现
整数幂运算
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);