关于java:16-数值的整数次方快速幂二分法int越界用long

16. 数值的整数次方

思路一：二分法 + 递归

< 自制 >
分为

• n 为 正 / 负 / 非凡 三种状况

• 其中，非凡又分为 0、±1 两种状况

  • 先将 n 为负的状况等效为 n 为正的状况，于是 poww 中只有两种状况；
  • 写出非凡状况以及 n 最根底的状况：n==2；
  • 二分法把 n /2, 再递归，直到 n == 2 或 1

• 最终后果要分 奇偶数 两种状况

  • 偶数就是

    x^(n/2)*x^(n/2)

  • 奇数就是(n/2 向下取整)

    x^(n/2)*x^(n/2)*x

• 留神：
  最初的奇偶 return 能够用三元运算符代替：

  return (n%2==0)?res*res:res*res*x;

  精简后：

  思路二：疾速幂

  
  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 才会乘

  操作：

的问题

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