231 Power of Two 2的冪
Description:
Given an integer, write a function to determine if it is a power of two.
Example:
Example 1:
Input: 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: 218
Output: false
題目描述:
給定一個(gè)整數(shù)，編寫一個(gè)函數(shù)來判斷它是否是 2 的冪次方撑毛。
示例：
示例 1:
輸入: 1
輸出: true
解釋: 2^0 = 1
示例 2:
輸入: 16
輸出: true
解釋: 2^4 = 16
示例 3:
輸入: 218
輸出: false
思路:
位操作
- 2的冪有且僅有 1位是1 n & (n - 1) 可以用來去掉最后一位的 1
- 如果 n是 2的冪, n & (-n) == n成立, -n的補(bǔ)碼只有最后一位跟 n相同且均為 1
補(bǔ)碼為正數(shù)的所有位取反再加 1
不妨設(shè) n用8位存儲(chǔ), n = 16 -> n = 00010000, -n = -16 -> -n = 11110000, n & -n = n - 如果 n是 2的冪, 那么 n一定能被 2 ^ 30整除(int最大為 2 ^ 31 - 1)
時(shí)間復(fù)雜度O(1), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
bool isPowerOfTwo(int n)
{
return n > 0 and (1 << 31) % n == 0;
}
};
Java:
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & n - 1) == 0;
}
}
Python:
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and -n & n == n
