美文网首页
Swift算法3-power of 2

Swift算法3-power of 2

作者: 四毛哥掉落的鳞片 | 来源:发表于2016-07-14 11:11 被阅读0次

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

    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!

    相关文章

      网友评论

          本文标题:Swift算法3-power of 2

          本文链接:https://www.haomeiwen.com/subject/jneejttx.html