关于java:offer-16-数值的整数次方

首先看到整数次方，就能够用 java 本人的 Math.pow 函数, 但本题要求不能应用库函数, 所以就会想到分状况探讨而后执行 for 循环，这样是对的，然而 超出工夫限度

因为 n 能够分为正负 0 三种状况，所以当 n 为正数的应用就是 - n 左，而后 x 变为 1 /x，而后利用 n 如果是偶数那就是 2 递归 n / 2 次，如果 n 是基数那就是 n / 2 次再多乘一个 x

二分法，递归很屡次，比拟耗内存

最初的奇偶 return 能够用三元运算符代替：
```
return (n%2==0)?res*res:res*res*x;
```

这个办法比拟离奇，有点意思
因为将 n 转为 2 进制数，能够将 n 变为 2 的几次幂，而后 x 的 n 次方，就能够变成 x 的 2 的几次幂的方相乘，即 n = 5，能够写成 101，即 5 = 1 2 的 2 +0 2 的 1 +1 2 的 0. 而后 x 的 5 次方就能够变为，x 的（1 2 的 2） x 的（0 2 的 1） x 的（1 2 的 0），也就是能够拆开乘

x 的 n 次方，把 n 转二进制：”bm…b3b2b1″
```
n = 1xb1+2xb2+4xb3+8xb4+16xb5+……+2^(m-1)bm
```

于是 x 的 n 次方变为：

X^[1xb1+2xb2+4xb3+8xb4+16xb5+……+2^(m-1)bm]
=X^[1xb1]X^[2xb2]X^[4xb3]X^[8xb4]……X^[2^(m-1)bm]
= 二进制位为 1 才会乘

留神右移的时候不必操作，间接移位即可，右移一位就是相当于除 2，所以就每次都乘 x 方，而后判断最初一位是 1 还是 0(和 1 与)，是 1 就多乘一个 x，不是就跳过间接返回

问题

将 n 存入 long 再 *-1，就能够防止，边界越界的谬误。（然而不晓得为什么思维一没有这个问题）

关于java:offer-16-数值的整数次方

数值的整数次方

题目剖析

题解

二分法加递归

疾速幂（二进制角度）

问题