n 的范围是[−2^31, 2^31 − 1],当 n = -2^31 时,执行 -n 操作会导致越界,所以需要将n转换成long类型来计算。
3.1 Java
class Solution {
public double myPow(double x, int n) {
/**
* 求 x ^ n
* n 的范围是 [−2^31, 2^31 − 1] 即 int 的范围
* 但是 -n 操作会导致越界,所以需要将 n 转换成 long 类型来计算
*/
long N = n;
if(N < 0) {
x = 1 / x;
N = -N;
}
/**
* 把指数 n 看成二进制数,比如 11 的二进制为 1011
* 11 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0
* x^11 = x^(2^3) * x^(2^1) * x^(2^0)
*/
double ans = 1;
// 指数不为0
while (N > 0) {
// 将N转换为二进制数,从最低位开始
// 如果当前位的二进制为1,那么就需要给 ans 乘上当前的 x
if (N % 2 == 1) {
ans *= x;
}
// x每一轮循环都要通过累乘来增加
x *= x; // 假设 x 的初始值为3,那么x的值为:3^(2^0), 3^(2^1), 3^(2^2) ...
// 解决完当前二进制位,将 N/2 继续求下一位
N /= 2; // 这里也可以用右移来代替:N >>= 1;
}
return ans;
}
}
3.2 Kotlin
class Solution {
fun myPow(x: Double, n: Int): Double {
var x = x
/**
* 求 x ^ n
* n 的范围是 [−2^31, 2^31 − 1] 即 int 的范围
* 但是 -n 操作会导致越界,所以需要将 n 转换成 long 类型来计算
*/
var N = n.toLong()
if (N < 0) {
x = 1 / x
N = -N
}
/**
* 把指数 n 看成二进制数,比如 11 的二进制为 1011
* 11 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0
* x^11 = x^(2^3) * x^(2^1) * x^(2^0)
*/
var ans = 1.0
// 指数不为0
while (N > 0) {
// 将N转换为二进制数,从最低位开始
// 如果当前位的二进制为1,那么就需要给 ans 乘上当前的 x
if (N % 2 == 1L) {
ans *= x
}
// x每一轮循环都要通过累乘来增加
x *= x // 假设 x 的初始值为3,那么x的值为:3^(2^0), 3^(2^1), 3^(2^2) ...
// 解决完当前二进制位,将 N/2 继续求下一位
N /= 2 // 这里也可以用右移来代替:N >>= 1
}
return ans
}
}