二进制搜索，看一个数字是2的幂

Question

我正在使用二进制搜索来检查数字是否为2的幂。我编写了下面的代码但是对于n = 2048我得到“OverflowError：（34，'结果太大'）”。

def isPowerOfTwo(n):

    if n <= 0:
        return False

    high = n
    low = 0
    mid = n/2
    print(high, low, mid)

    while True:
        if mid.is_integer() and 2**mid == n:
            print(high, low, mid)
            return True
        elif mid.is_integer() and 2**mid > n:
            print(high, low, mid)
            high = mid
            mid = (high + low) / 2
        elif mid.is_integer() and 2**mid < n:
            print(high, low, mid)
            low = mid
            mid = (high + low) / 2            
        else:
            print(high, low, mid)
            return False

Answer 1

你也可以使用二进制运算（而不是二进制搜索），二进制的幂是1，后面只有0。这是测试的一种方法：

def isPowerOfTwo(n):

    if n <= 0:
        return False

    # get rid of all the trailing zeros
    while not n & 1:
        n >>= 1

    if n != 1:
        return False
    else:
        return True

或者只是（可能更快）

def isPowerOfTwo(n):

    if n <= 0:
        return False
    return bin(n).count("1") == 1

Answer 2

您可以修改n以涵盖以下三种情况之一：

1. n = 2，在这种情况下，return True
2. n % 2非零，所以它不是2的倍数，return False
3. 两者都没有，用n //= 2更新为整数除法：

def my_func(n):
    if n<=0:
        return False

    elif n==1 or n==2:
        return True

    while n:
        if n==2:
            return True
        elif n%2:
            return False
        else:
            n//=2

    # At the end of your loop, n will be zero, indicating that it was a power of 2
    return True