binary search to see if a number a power of 2

Question

I am using binary search to check if a number is a power of 2. I wrote the code below but for n = 2048 I get "OverflowError: (34, 'Result too large')".

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

Why are you defining your `high` as `n` (and `mid` as `n/2`) ? It is supposed to be the power of two, not the number itself — Eugene Sh., Mar 27 '19 at 18:23
If n is 2048, then mid = 1024, and `2**mid` is 2 ** 1024, which is quite a large number... — John Gordon, Mar 27 '19 at 18:23
`n` here should be an integer by default, so you shouldn't need to type-check. Also, try working down from `n` using `n//=2` in your loop. That way you can use `while n:` — C.Nivs, Mar 27 '19 at 18:25
Besides your algorithm and the question, note checking if a number is a power of two can be reduced to checking that it contains a single `1` bit (see [Fast way of counting non-zero bits in positive integer](https://stackoverflow.com/q/9829578)). Or, if you are not considering arbitrarily big integers, you can have a set of powers of two (like `pow_of_2 = {1 << i for i in range(64)}`) and just check if it's in there. — jdehesa, Mar 27 '19 at 18:27
If you're dividing by two anyway, I'd just do that repeatedly and check the modulo. No need to also do exponentiation. — Kenny Ostrom, Mar 27 '19 at 18:27

score 2 · Answer 1 · answered Mar 27 '19 at 18:28

you could also use binary operations (instead of a binary search), a power of to in binary is a 1 followed by 0 only. this is one way to test for that:

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

or just (and probably faster)

def isPowerOfTwo(n):

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

score 0 · Answer 2 · answered Mar 27 '19 at 18:30

You can modify n to cover one of three cases:

n = 2, in which case, return True
n % 2 is nonzero, so it is not a multiple of 2, return False
Neither, update with n //= 2 which is integer-divide:

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

binary search to see if a number a power of 2

2 Answers2