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/09/09 08:03:33
C语言有关快速幂问题求帮忙解释下这哥函数的原理.doublepow(doublex,intn){\x09doubleans=1,tem=x;\x09while(n)\x09{\x09\x09if(n&
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等价,便于理解),如果奇书就单独乘一个.
大概就是这个意思,可以减少乘法运算次数.