50.Pow 次方解法

50.Pow 次方解法

算法

以2的六次方來說

2乘以六次，如果有一萬次的話，就要乘以一萬次，這做法肯定是不行的，花太多時間

我們可以發現

2的6次方等於4的3次方

4的3次方等於16的1次方乘以4

我們思考一下什麼情況下會多出 4 這個數字

當次方是奇數的時候，會多出一個無法成對的數字

總和可以分成底數和額外數值，相乘就是最後的答案

算到何時結束

這個算法是一個無限循環，直到次方小於等於0

1. 判斷次方是不是奇數，是的話底數乘以額外數值
2. 底數自乘一次
3. 次方除以2

這個循環之下我們可以得到越來越大的底數和越來越小的次方直到次方為0

並且可以把無法成對的數值而外使用一個數值去記起來

n 次方

base 額外數值

x 底數

while (n > 0){
  if((n&1) > 0){
      base *= x;
  }
  x *= x;
  n >>= 1;
}

該注意的點

這個題目次方會給你負數的

2的2次方為例子

正的為4

負的為 1/ 4

界線

2的-31次方 -2147483648要注意

取絕對值的時候會比整數2147483647還大，會造成計算錯誤

如果底數是 1 或 -1 答案是 1

底數如是其他數值 答案是0，因為 1除以 1以上的2147483648次方，數值接近於0