Implement
pow(x, n)
, which calculatesx
raised to the powern
.
Note:
- -100.0 <
x
< 100.0n
is a 32-bit signed integer, within the range[−231, 231 − 1]
實作 pow(x, n),也就是計算
x
的n
次方。
注意:
- -100.0 <
x
< 100.0n
是三十二位元的有號整數,其範圍在[−231, 231 − 1]
return pow(x, n);
也會過,但這樣就沒有意義了XDSquare and multiply
,簡單來說是將n
的部分藉由自己乘自己來大幅加速。
2^9
我們可以想成2*2*2*2*2*2*2*2*2
= 8
次乘法。2*2=4
,然後將式子改為2*4*4*4*4
= 5
次乘法。4*4=16
,最後變為2*16*16
= 4
次乘法。v = 1
去存結果,並將n
想成是二進制碼(9 = 1001
)1
,v *= x
n
往右位移,並將x *= x
。n = 0
。Square and multiply
了,其實並不難理解。x
為整數的情況下,該演算法還可以加入取餘數的功能,讓整體速度更加提升。
n
可能是負數,此時只需要將n
轉回正數,並將v *= x
改為v /= x
即可。n
是否超出範圍,適時的轉換型態或其他處理。LeetCode
C++