今天看到一個小算法挺有意思。如何判斷一個整數是2的幂。
假設整數為v,v如果是2的幂,需具備一個特點,它的二進制位中隻有一位是1。于是可以通過判斷它的二進制位中有多少個1, 結果有且隻有1個1,就是2的幂。
寫出代碼就是:
到這裡本來該結束了,發現還有更簡單的辦法, 如下
一開始看,沒有太明白。 val & ( val - 1) == 0,就說明了val是2的幂?
還得從二進制的角度來看,val既然是2的幂,則val中有且隻能有一位是1,其餘位全為0,二進制可以寫成形式
val = x0.x1.x2.x3..xk.xk 1….xn
假設xk位為1,其餘位為0,則 n = val-1的結果是 從xk 1開始到xn全部變為1,而x0到xk全部為0
這樣的話 val & n 就為0了。而如果 val中不止1個1,則n & val不可能為0, 因此隻要滿足
val & n == 0,就能說明val是2的幂。
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!