Swift算法3-power|Swift算法3-power of 2
Given an integer, write a function to determine if it is a power of two.
四种方法：（可以看一下迭代和递归的区别）
- 迭代 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)))
}
}
【Swift算法3-power|Swift算法3-power of 2】3.bit O(1):
因为2的n次方的二进制表示法 & 2的n次方－1的二进制表示法 的值为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.
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!
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Swift中willSet和didSet的简述
- 《算法》-图[有向图]
- Hacking|Hacking with iOS: SwiftUI Edition - SnowSeeker 项目（一）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列