C语言有关快速幂问题求帮忙解释下这哥函数的原理.double pow(double x,int n){\x09double ans = 1,tem = x;\x09while (n)\x09{\x09\x09if (n & 1)\x09\x09\x09ans *= tem;\x09\x09tem *= tem;\x09\x09n >> 1;\x09}\x09return ans;}
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/25 10:40:38
![C语言有关快速幂问题求帮忙解释下这哥函数的原理.double pow(double x,int n){\x09double ans = 1,tem = x;\x09while (n)\x09{\x09\x09if (n & 1)\x09\x09\x09ans *= tem;\x09\x09tem *= tem;\x09\x09n >> 1;\x09}\x09return ans;}](/uploads/image/z/3756779-35-9.jpg?t=C%E8%AF%AD%E8%A8%80%E6%9C%89%E5%85%B3%E5%BF%AB%E9%80%9F%E5%B9%82%E9%97%AE%E9%A2%98%E6%B1%82%E5%B8%AE%E5%BF%99%E8%A7%A3%E9%87%8A%E4%B8%8B%E8%BF%99%E5%93%A5%E5%87%BD%E6%95%B0%E7%9A%84%E5%8E%9F%E7%90%86.double+pow%28double+x%2Cint+n%29%7B%5Cx09double+ans+%3D+1%2Ctem+%3D+x%3B%5Cx09while+%28n%29%5Cx09%7B%5Cx09%5Cx09if+%28n+%26+1%29%5Cx09%5Cx09%5Cx09ans+%2A%3D+tem%3B%5Cx09%5Cx09tem+%2A%3D+tem%3B%5Cx09%5Cx09n+%3E%3E+1%3B%5Cx09%7D%5Cx09return+ans%3B%7D)
C语言有关快速幂问题求帮忙解释下这哥函数的原理.double pow(double x,int n){\x09double ans = 1,tem = x;\x09while (n)\x09{\x09\x09if (n & 1)\x09\x09\x09ans *= tem;\x09\x09tem *= tem;\x09\x09n >> 1;\x09}\x09return ans;}
C语言有关快速幂问题
求帮忙解释下这哥函数的原理.
double pow(double x,int n)
{
\x09double ans = 1,tem = x;
\x09while (n)
\x09{
\x09\x09if (n & 1)
\x09\x09\x09ans *= tem;
\x09\x09tem *= tem;
\x09\x09n >> 1;
\x09}
\x09return ans;
}
C语言有关快速幂问题求帮忙解释下这哥函数的原理.double pow(double x,int n){\x09double ans = 1,tem = x;\x09while (n)\x09{\x09\x09if (n & 1)\x09\x09\x09ans *= tem;\x09\x09tem *= tem;\x09\x09n >> 1;\x09}\x09return ans;}
原理就是n^4=(n^2)^2
偶数次幂可以拆解,这样利用位运算,二进制末尾1的是奇数,末尾0的是偶数,因此每次就是幂指数除以2(n>>1等价,便于理解),如果奇书就单独乘一个.
大概就是这个意思,可以减少乘法运算次数.