Swift算法3-power|Swift算法3-power of 2

Given an integer, write a function to determine if it is a power of two.
四种方法:(可以看一下迭代和递归的区别)

  1. 迭代 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) } }

  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) } }

  1. 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!

    推荐阅读