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

示例?1:

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

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

輸入: 218
輸出: false

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

?

什么是lowbit運算？

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

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

lowbit(n) = n & -n

公式證明

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

n >= 0： n的補(bǔ)碼就是它本身
n < 0： n的補(bǔ)碼為~n + 1，其中~n為n的反碼
我們可以通過一個通例來證明，假設(shè)n=101...1000，中間的數(shù)字省略，直到展示出最右邊的一個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后，解決本題的思路就非常簡單了，一行代碼就可以解決。因為我們可以發(fā)現(xiàn)，2的整數(shù)冪都只包含一個1。換句話說n是2的整數(shù)冪，則lowbit(n) == n。

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

總結(jié)

以上是生活随笔為你收集整理的leetcode 231. 2的幂的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。