验证2的整数幂

问题

如何检验一个数是否是2的整数幂？

解法

暴力检验

最直观的正向思考，如果一个数 a 是2的整数次幂，则1的 n 次幂等于 a 。

def is_power_of2(num):
    tmp = 1
    while tmp <= num:
        if tmp == num:
            return True
        tmp *= 2
    return False

反向思考，如果一个数 a 是2的整数幂，则它可以一直被2整除，直到商为1。

def is_power_of2(num):
    while num >= 0:
        if num == 1:
            return True
        num, remainder = divmod(num, 2)
        if remainder != 0:
            return False
    return False

这两种方法的时间复杂度都是 \(O(logn)\)

位运算

一个2的整数幂的值，用二进制表示是 1000 形式，而它与比它小1的值与运算就会变为0：

1000&111=0

于是可以得到一个简单的判断方法：

def is_power_of2(num):
    return num & (num - 1) == 0