Given an integer, write a function to determine if it is a power of two.
四種方法：（可以看一下迭代和遞歸的區(qū)別）
- 迭代 O(log n)：
class Solution {
func isPowerOfTwo(var n: Int) -> Bool {
if (n == 0) {
return false
} else {
while (n % 2 == 0) {
n /= 2
}
}
return (n == 1)
}
}
- 遞歸 O(log n):
class Solution2 {
func isPowerOfTwo1(var n: Int) -> Bool {
return n > 0 && (n == 1 || (n % 2 == 0 && isPowerOfTwo1(n / 2)))
}
}
3.bit O(1):
因為2的n次方的二進(jìn)制表示法 & 2的n次方－1的二進(jìn)制表示法 的值為0
class Solution {
func isPowerOfTwo(n: Int) -> Bool {
return n > 0 && (n & (n - 1) == 0)
}
}
- Math O(1):
Because the range of an integer = -2147483648 (-2^31) ~ 2147483647 (2^31-1), the max possible power of two = 2^30 = 1073741824.
(1) If n is the power of two, let n = 2^k, where k is an integer.
We have 2^30 = (2^k) * 2^(30-k), which means (2^30 % 2^k) == 0.
(2) If n is not the power of two, let n = j*(2^k), where k is an integer and j is an odd number.
We have (2^30 % j*(2^k)) == (2^(30-k) % j) != 0.
class Solution {
func isPowerOfTwo(n: Int) -> Bool {
return n > 0 && (1073741824 % n == 0)
}
}
But is the last solution do-able?
I don't like the last solution!
