前陣子，有小伙伴在我B站的算法教程底下留言

小伙伴們有任何疑問或者希望我解說任何內容，都可以在我的小我私家B站或民眾號(xmg_mj)留言哦，我會盡我最大能力、只管抽時間去寫文章\錄視頻來回應人人。

關于快速冪

實在快速冪相關的問題，是加入算法競賽(NOI、ACM等)的小伙伴必須要掌握的一小塊基礎內容。固然，就算你不設計加入算法競賽，小我私家以為只要你是一名程序員，就必須要掌握快速冪算法。

在《計算機程序設計藝術》一書中就有提到快速冪算法，此書的英文名是The Art of Computer Programming，簡稱TAOCP。

TAOCP出自Donald Ervin Knuth先輩之手。Knuth先輩是在計算機領域成就頗豐的著名科學家，是著名的KMP算法的發明人之一，在1974年獲得“計算機領域的諾貝爾獎”：圖靈獎(昔時他才36歲)。現在TAOCP已經出書了第1、2、3、4A卷，憑據設計，另有第4B、5、6、7卷未出書。第一卷首發于1968年，Knuth先輩今年是82歲高壽，聽說他設計在105歲之前完成這部巨著。

關于TAOCP，微軟創始人Bill Gates曾說過

If you think you’re a really good programmer… read (Knuth’s) Art of Computer Programming… You should definitely send me a resume if you can read the whole thing.

也許意思是：若是你以為自己是一位異常優異的程序員，那就應該閱讀Knuth的TAOCP；若是你能讀懂全部內容，可以直接給我發送一份簡歷。聽說Knuth先輩的言辭加倍犀利：看不懂就別當程序員了！不外TAOCP對于新手來說，閱讀難度簡直對照大，書中的所有示例都使用了Knuth先輩自創的MIX匯編語言。

閱讀本文之前的提醒

今天就抽閑寫一篇文章來解說一下經典的快速冪算法哈。不外要想徹底看懂本文，有幾個前提條件

熟悉算法中的2個基礎觀點：時間復雜度、空間復雜度

若是你壓根沒聽過這2個觀點，說明你的算法基礎完全為0，真的沒有在開頑笑！

可以向民眾號發送復雜度獲取相關教程

熟悉二進制和十進制的轉換

若是連這個都不熟悉的話，那你的編程基礎就真的需要好好補補啦

可以向民眾號發送進制獲取相關教程

熟悉常見的位運算操作

n & 1的效果是n最低二進制位的值，也可以用于判斷n的奇偶性

求正整數n / 2，可以用位運算取代：n >> 1

若是不明白上述操作的原理，可以向民眾號發送位運算獲取相關教程

什么是冪(Power)？

眾所周知，x的n次冪，是指x的n次方，也就是n個x相乘，好比2的4次冪就是2 * 2 * 2 * 2。

為了簡化形貌，后面x的n次冪，我就簡化為x ^ n(本文中的 ^ 并不是按位異或的意思)

那若何通過編程求冪？假設只思量x、n是整數且n大于即是0的情形，最容易想到的方式如下所示(這里接納的編程語言是Java，但沒有涉及Java特殊的語法。以是就算你沒用過Java，也可以看懂)

int power(int x, int n) {

int result = 1;

while (n-- > 0) {

result *= x;

}

return result;

}

很顯然，這種方式的時間復雜度是O(n)、空間復雜度是O(1)

什么是快速冪？

所謂快速冪，就是用效率更高(時間復雜度更低)的方式求冪，可以將時間復雜度優化至O(logn)。這里先容2種求解方式：遞歸、非遞歸

遞歸

憑據上圖中的等式，不難寫出以下代碼

int fastPower(int x, int n) {

if (n == 0) return 1;

int result = fastPower(x, n >> 1);

result *= result;

return (n & 1) == 0 ? result : result * x;

}

這個方式的時間、空間復雜度都是O(logn)。

那若何剖析出這個方式的復雜度呢？

若是你的算法功底對照微弱，可以代入特定值作一個也許的剖析，好比當n為16時，方式的遞歸挪用歷程如下圖所示

不難看出，每次挪用時，n的規模都減半，以是時間和空間復雜度都是O(logn)

若是你的算法功底還行，那就可以用更專業的方式去剖析它的復雜度(沒有一定的算法基礎，可能會看不懂)

這實在是典型的應用分治計謀的算法

假設T(n)是數據規模為n時的時間復雜度，不難得出遞推式：T(n) = T(n / 2) + O(1)

最后憑據遞推式 + 主定理(Master Theorem)可以直接得出結論：T(n) = O(logn)

非遞歸

我們以求3 ^ 21為例子，來剖析一下非遞歸的代碼應該怎么寫。

首先21的二進制形式是10101

不難得出以下結論

3 ^ n(n為2、4、8、16)都可以由3 ^ 1累乘出來

每一個3 ^ n都有對應的二進制位

3 ^ 1對應二進制位的值是1，實在是二進制10101的最后1位

3 ^ 2對應二進制位的值是0，實在是二進制1010的最后1位

3 ^ 4對應二進制位的值是1，實在是二進制101的最后1位

3 ^ 8對應二進制位的值是0，實在是二進制10的最后1位

3 ^ 16對應二進制位的值是1，實在是二進制1的最后1位

若是3 ^ n對應二進制位的值是0，就不用乘進最終效果

好比3 ^ (8 * 0)、3 ^ (2 * 0)

由于它們最終的值都是3 ^ 0，也就是1

若是3 ^ n對應二進制位的值是1，就需要乘進最終效果

好比3 ^ (16 * 1)、3 ^ (4 * 1)、3 ^ (1 * 1)

以是，綜合以上種種結論，可以總結出以下解題步驟

行使3 ^ 1，不停累乘出3 ^ n(n為2、4、8、16)

每當累乘出一個3 ^ n，就查看其對應二進制位的值是1照樣0，來決議是否要將它乘進最終效果

int fastPower(int x, int n) {

int result = 1;

while (n != 0) {

if ((n & 1) == 1) {

result *= x;

}

x *= x;

n >>= 1;

}

return result;

}

代入3和21，fastPower(3, 21)的執行流程如下

第1輪while循環

第4行代碼

n的二進制是10101(十進制是21)

x = 3 ^ 1, 其對應二進制位的值是1(n的最后一個二進制位)

以是需要執行第5行代碼：將x乘進最終效果

result = 3 ^ 1

第7行代碼

x = (3 ^ 1) * (3 ^ 1) = 3 ^ 2

第8行代碼

n右移1位，其二進制變成了1010(對應的十進制是啥？不重要！！！)

第2輪while循環

第4行代碼

n的二進制是1010

x = 3 ^ 2, 其對應二進制位的值是0(n的最后一個二進制位)

以是不需要執行第5行代碼：不需要將x乘進最終效果

result = 3 ^ 1

第7行代碼

x = (3 ^ 2) * (3 ^ 2) = 3 ^ 4

第8行代碼

n右移1位，其二進制變成了101(對應的十進制是啥？不重要！！！)

第3輪while循環

第4行代碼

n的二進制是101

x = 3 ^ 4, 其對應二進制位的值是1(n的最后一個二進制位)

以是需要執行第5行代碼：將x乘進最終效果

result = (3 ^ 1) * (3 ^ 4)

第7行代碼

x = (3 ^ 4) * (3 ^ 4) = (3 ^ 8)

第8行代碼

n右移1位，其二進制變成了10(對應的十進制是啥？不重要！！！)

第4輪while循環

第4行代碼

n的二進制是10

x = 3 ^ 8, 其對應二進制位的值是0(n的最后一個二進制位)

以是不需要執行第5行代碼：不需要將x乘進最終效果

result = (3 ^ 1) * (3 ^ 4)

第7行代碼

x = (3 ^ 8) * (3 ^ 8) = 3 ^ 16

第8行代碼

n右移1位，其二進制變成了1(對應的十進制是啥？不重要！！！)

第5輪while循環

第4行代碼

n的二進制是1

x = 3 ^ 16, 其對應二進制位的值是1(n的最后一個二進制位)

以是需要執行第5行代碼：將x乘進最終效果

result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)

第7行代碼

x = (3 ^ 16) * (3 ^ 16) = 3 ^ 32

第8行代碼

n右移1位，其二進制變成了0

最后

由于n = 0，以是退出while循環

最終result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)

復雜度剖析

每執行一次while的循環體，n >>= 1, 會導致n的值減半

以是時間復雜度：O(logn)、空間復雜度：O(1)

Leetcode

Leetcode上的第50號題50. Pow(x, n)，恰好就可以用今天解說的快速冪算法。以下是我的代碼實現

// 遞歸

public double myPow(double x, int n) {

if (n == 0) return 1;

if (n == -1) return 1 / x;

double half = myPow(x, n >> 1);

half *= half;

return ((n & 1) == 1) ? half * x : half;

}

// 非遞歸

public double myPow(double x, int n) {

long y = (n < 0) ? -((long) n) : n;

double result = 1.0;

while (y > 0) {

if ((y & 1) == 1) {

result *= x;

}

x *= x;

y >>= 1;

}

return (n < 0) ? (1 / result) : result;

}

需要提醒的是

這里我用的編程語言是Java，人人可以憑據自己熟悉的編程語言，對一些語法細節作出響應的調整

Leetcode上的n可能是個負數，以是上面的代碼針對負數的情形作了一些處置

更多快速冪相關的問題

時間有限，這篇文章就先說到這了哈。給小伙伴們留2個快速冪相關的問題，有空的話，可以去研究一下

使用矩陣快速冪求斐波那契數列

請設計一個算法求x的y次冪模z的效果：(x ^ y) % z

假設x、y都可能是很大的整數(y大于即是0，z不即是0)

若是你稀奇希望我寫點什么方面的內容，也可以留言建議，謝謝。迎接關注

原文鏈接：https://www.cnblogs.com/mjios/p/12690097.html

本站聲明:網站內容來源于網絡,若有侵權,請聯系我們,我們將及時處置。

總結

以上是生活随笔為你收集整理的java位运算求幂,程序员必学：快速幂算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。