給定一個整數，編寫一個函數來判斷它是否是 2 的冪次方。

示例?1:

輸入: 1
輸出: true
解釋: 20?= 1
示例 2:

輸入: 16
輸出: true
解釋: 24?= 16
示例 3:

輸入: 218
輸出: false

本題思路轉載位運算的常用技巧：lowbit運算，包含lowbit公式、講解、證明

?

什么是lowbit運算？

lowbit(n)運算是一個位運算的常用技巧，本題就可以直接用lowbit運算解決。
它的作用是求出n在表示成二進制的時候，最右邊的1出現的位置對應的數。這么說有點晦澀，看倆例子就懂了，其實很簡單：

lowbit(4) = lowbit(100) = 100
lowbit(5) = lowbit(1001) = 1
lowbit(6) = lowbit(1010) = 10
lowbit公式
lowbit公式非常簡單：

lowbit(n) = n & -n

公式證明

大家需要有一點計算機組成原理的常識，具體的我這里就不詳述了，只簡單提一下。在計算機中，數據的存儲是以補碼的形式，對于補碼來說：

n >= 0： n的補碼就是它本身
n < 0： n的補碼為~n + 1，其中~n為n的反碼
我們可以通過一個通例來證明，假設n=101...1000，中間的數字省略，直到展示出最右邊的一個1。

lowbit(n) = n & -n = n & (~n + 1)
n = ? ? ?101...1000
~n = ? ? 010...0111
~n + 1 = 010...1000
因此lowbit(n) = n & (~n + 1) = 1000

本題的解答

知道了lowbit后，解決本題的思路就非常簡單了，一行代碼就可以解決。因為我們可以發現，2的整數冪都只包含一個1。換句話說n是2的整數冪，則lowbit(n) == n。

class Solution {public boolean isPowerOfTwo(int n) {return n > 0 && (n & -n) == n;}
}