LCOF16 快速幂

链接 lcof16 快速幂

描述 实现函数double Power(double base, int exponent)，求base的exponent次方。

分析

十进制正整数n，二进制表示“bm…b3b2b1”二进制转十进制，n = 1b1 + 2b2 + 4b3 + … + 2^(m-1)bm所以计算每一个二进制位的幂(x¹，x² ，x⁴，…)，将所有位的幂相乘利用移位操作，每计算一位去掉右边的一个1幂指数n为负数时，底数x转为1/x，指数取绝对值

代码

class Solution { public: double myPow(double x, int n) { if(x == 0) return 0;//底数为0 long b = n;//记录二进制位 double res = 1.0; if(b < 0) {//幂指数为负数 x = 1 / x; b = -b; } while(b > 0) {//遍历幂指数二进制位 if((b & 1) == 1) res *= x;//各二进制位指数运算结果相乘 x *= x;//计算各二进制位指数基 b >>= 1; } return res; } };

扩展 考虑到大数问题，高次幂可能超出表示范围，利用取模运算

class Solution { public: double myPow(double x, int n) { if(x == 0) return 0;//底数为0 long b = n;//记录二进制位 double res = 1.0; int mod = 2333; if(b < 0) {//幂指数为负数 x = 1 / x; b = -b; } while(b > 0) {//遍历幂指数二进制位 //各二进制位指数运算结果相乘 if((b & 1) == 1) res = (res * x) % mod; x = (x * x) % mod;//计算各二进制位指数基 b >>= 1; } return res; } };