# O(1) Check Power of 2 ### Source - lintcode: [(142) O(1) Check Power of 2](http://www.lintcode.com/en/problem/o1-check-power-of-2/) ~~~ Using O(1) time to check whether an integer n is a power of 2. Example For n=4, return true; For n=5, return false; Challenge O(1) time ~~~ ### 題解 咋看起來挺簡單的一道題目，可之前若是沒有接觸過神奇的位運算技巧遇到這種題就有點不知從哪入手了，咳咳，我第一次接觸到這個題就是在七牛的筆試題中看到的，淚奔 :-( 簡單點來考慮可以連除2求余，看最后的余數是否為1，但是這種方法無法在 O(1)O(1)O(1) 的時間內解出，所以我們必須要想點別的辦法了。2的整數冪若用二進制來表示，則其中必只有一個1，其余全是0，那么怎么才能用一個式子把這種特殊的關系表示出來了？傳統的位運算如按位與、按位或和按位異或等均無法直接求解，我就不賣關子了，比較下`x - 1`和`x`的關系試試？以`x=4`為例。 ~~~ 0100 ==> 4 0011 ==> 3 ~~~ 兩個數進行按位與就為0了！如果不是2的整數冪則無上述關系，反證法可證之。 ### Python ~~~ class Solution: """ @param n: An integer @return: True or false """ def checkPowerOf2(self, n): if n < 1: return False else: return (n & (n - 1)) == 0 ~~~ ### C++ ~~~ class Solution { public: /* * @param n: An integer * @return: True or false */ bool checkPowerOf2(int n) { if (1 > n) { return false; } else { return 0 == (n & (n - 1)); } } }; ~~~ ### Java ~~~ class Solution { /* * @param n: An integer * @return: True or false */ public boolean checkPowerOf2(int n) { if (n < 1) { return false; } else { return (n & (n - 1)) == 0; } } }; ~~~ ### 源碼分析 除了考慮正整數之外，其他邊界條件如小于等于0的整數也應考慮在內。在比較0和`(n & (n - 1))`的值時，需要用括號括起來避免優先級結合的問題。 ### 復雜度分析 O(1)O(1)O(1). ### 擴展 關于2的整數冪還有一道有意思的題，比如 [Next Power of 2 - GeeksforGeeks](http://www.geeksforgeeks.org/next-power-of-2/)，有興趣的可以去圍觀下。