Interview Question: How to Check Integer is the Power of Two?

This is a possible interview question.
Q: List three methods of checking whether any given integers are the power of 2. i.e. and compare the algorithm complexity and performance.

A: The first one is bruteforce, the complexity is Checking every possible answer until the value of is larger than the given integer. This is slow but straightforward. The second solution is to compute directly the value of and check if its fraction is zero. This is fast, but it may have a precision problem because of the floating point computation and comparison. The complexity is . The last solution is the most efficient and fastest without problems. It is based on the idea that if an integer is power of two, its binary representation will have a single one only. Minus one and do the and operation will be zero for these numbers. The complexity is also . The Python code for these solutions is given below and the timing proves that the above analysis is correct.

from math import log, floor
from time import time

def chk1(n):
    if n < 1:
        return False
    if n <= 2: # 2^0 = 1, 2^1 = 2
        return True
    i = 2
    while True:
        i *= 2
        if i == n:
            return True
        if i > n:
            return False

def chk2(n):
    if n < 1:
        return False
    i = log(n, 2)
    # might have precision problem
    return abs(i - floor(i)) <= 1e-9 

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

def test(n, x):
    for i in xrange(0, int(n)): # launch n tests
        x(i)

if __name__ == "__main__":
    time1 = time();
    test(1e6, chk1)
    print "chk1 = %.5f" % (time() - time1)

    time1 = time();
    test(1e6, chk2)
    print "chk2 = %.5f" % (time() - time1)

    time1 = time();
    test(1e6, chk3)
    print "chk3 = %.5f" % (time() - time1)

The performance timings are:

chk1 = 2.92900
chk2 = 0.68100
chk3 = 0.21800

It is obvious that the integer method chk3 is the most efficient among the three.

See also: Teaching Kids Programming – Algorithms of Power of Two and C++ Function to Check if Integer is Power of Two

–EOF (The Ultimate Computing & Technology Blog) —