int mi(int p,int c){ int ans=1; for(;c;c>>=1){ if(c&1==1)ans*=p; p*=p; } return ans; }
时间: 2024-05-20 19:13:32 浏览: 44
fast_ber:C ++ 11 ASN.1 BER编码和解码库
这是一个快速幂算法的实现,用于求解 $p^c$ 的值,其中 $p$ 和 $c$ 均为正整数。该算法的时间复杂度为 $O(\log c)$,比直接进行 $c$ 次乘法运算更加高效。
具体实现过程如下:
1. 初始化 ans=1。
2. 循环迭代,每次判断 c 是否大于 0,如果 c=0 则跳出循环。
3. 判断 c 的当前二进制位是否为 1,如果是则将 ans 乘上 p。
4. 将 p 自乘一次,表示将底数平方。
5. 将 c 右移一位,相当于将指数除以 2。
6. 返回 ans。
例如,调用 mi(2,5) 函数,其执行过程如下:
1. 初始化 ans=1。
2. 循环迭代,第一次迭代时,c=5>0,继续执行;
3. 判断 c 的当前二进制位是否为 1,5 的二进制为 101,最低位为 1,ans=2;
4. 将 p 自乘一次,p=4;
5. 将 c 右移一位,c=2;
6. 第二次迭代,c=2>0,继续执行;
7. 判断 c 的当前二进制位是否为 1,2 的二进制为 10,最低位为 0,ans=2;
8. 将 p 自乘一次,p=16;
9. 将 c 右移一位,c=1;
10. 第三次迭代,c=1>0,继续执行;
11. 判断 c 的当前二进制位是否为 1,1 的二进制为 1,最低位为 1,ans=32;
12. 将 p 自乘一次,p=256;
13. 将 c 右移一位,c=0;
14. 跳出循环,返回 ans=32。
因此,mi(2,5) 的返回值为 32。
阅读全文