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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | 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) |
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) —
loading...
Last Post: Interview Question: Simple Division
Next Post: Runlength Compression Algorithm, Demonstration in Python