当前位置: 代码迷 >> 综合 >> 一个求幂的小trick
  详细解决方案

一个求幂的小trick

热度:11   发布时间:2024-01-15 21:21:04.0

naive版的求幂函数很单纯,复杂度O(N)。

能否简化计算呢?我们来分析一哈~

求m^n,假设 n = 13。n表示成2进制为1101,即13 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0

m ^ n = m ^ (8 + 4 + 1) = m ^ 8 * m ^ 4 * m^ 1

here it is !

m^n可以拆分成最多log(n)个数相乘,且这些数的关系为:相邻两数前者是后者的平方。

且由于每次res去乘以的数(如果该位为0则不乘)都是上一次那个数的平方, 所以,这个数我用完一次,

就对它取平方,准备下一次的使用即可。

code如下:

int myPow(int m, int n)
{int res = 1;while(n){if(n & 1)res *= m;m *= m;n >>= 1;}return res;
}