快速幂

算一个数的n次方怎么乘最省？

image.png

  • t 乘自己
  • n的二进制有多少位，t就跟自己玩多少回
  • 上面这种情况是只适用于n是正数的情况，

若n是负数，那么这样可以把n转成正数，最后再用1除以结果
image.png
但若n是系统最小转不了，怎么处理系统最小？（X^系统最小） (系统最小转不成正数)

  • 先算X ^ (系统最小 + 1), 得到ans
  • 最后再把ans * X
  • 若X绝对值小于1， 和x绝对值大于1 ，绝对不用想，溢出，直接返回0即可
  • 只用判断x绝对值等于1的情况 
  1. public double myPow(double x, int n) {
  2.     if (n == 0) {
  3.         return 1D;
  4.     }
  5.     int pow = Math.abs(n == Integer.MIN_VALUE ? n + 1 : n);
  6.     double t = x;
  7.     double ans = 1D;
  8.     while (pow != 0) {
  9.         if ((pow & 1) != 0) {
  10.             ans *= t;
  11.         }
  12.         pow >>= 1;
  13.         t *= t;
  14.     }
  15.     if (n == Integer.MIN_VALUE) {
  16.         ans *= x;
  17.     }
  18.     return n < 0 ? (1D / ans) : ans;
  19. }