python实现判断一个数是否是2的n次方

算法1：构造法

对1进行移位操作，即从1开始产生$2^0,2^1,2^2···$20,21,22⋅⋅⋅，如果产生的数相等，则该数是2的n次方，如果产生的数小于该数，则继续移位，如果产生的数大于该数，则该数不是2的n次方。

python实现

def is_two_power(n):
    if n < 1:
        return False
    i = 1
    while i <= n:
        if i == n:
            return True
        i <<= 1
    return False


def main():
    print(is_two_power(8))
    print(is_two_power(9))


if __name__ == '__main__':
    main()

输出：

True
False

复杂度分析

设给定数为$n$n，算法运行$k$k次，则$2^k=n$2k=n，$k=\log_2(n)$k=log2​(n)，因此复杂度为$o(log_2(n))$o(log2​(n))。

算法2：与操作法

对$2^0,2^1,2^2···$20,21,22⋅⋅⋅进行分析，其二进制分别为1,10,100···，如果n&(n-1)=0，则该数是2的n次方，反之不是2的n次方。

python实现

def is_two_power(n):
    if n < 1:
        return False
    m = n & (n - 1)
    return m == 0


def main():
    print(is_two_power(8))
    print(is_two_power(9))


if __name__ == '__main__':
    main()

输出：

True
False

复杂度分析

仅比较一次，复杂度为$o(1)$o(1)