6. Check if number is power of 2 #
Created Monday 29 June 2020
A number which is a power of 2 is of the form:
000...1...000;// 1 is at the ith bit(unknown)
Solutions:
- While Loop - Divide by 2 if possible, if we reach 1 return true ⇒ O(logn)
- Count number of 1’s in the binary representation ⇒ O(1) ⇒ 32 or 64 steps - Clumsy needs a for loop
- return (n & (n-1))==0
Inspiration - Observing that a power of 2 has all 0’s except one, and n-1 of that has all 1’s but just before the 1 in n ⇒ (n& n-1) = 0 for powers of 2. Then checking if the reverse is true. No counter example found, so tried to prove that it works only for powers of 2. isPower of 2 theorem **To prove: **n is power of 2 ⇔ n&(n-1) is 0
- If n is a power of 2 ⇒ n&(n-1) is 0
n = 0…10…0 n-1 = 0…01…1 n & n-1 = 0…0 Proved
- If n&(n-1) is 0 ⇒ n is a power of 2
If n is odd: n = 0…edcba1 n - 1= 0…edcba0 ans = n & (n-1) = 0…edbca0 ∵ x & x = x ans = 0 iff all edcba are 0 ⇒ only n=1 is the odd power of 2. And the theorem works. If n is even(with more than 1 ones): Case 1: only 1 one By definition correct, works. Case 2: Aleast two ones n = 0…0edcba0…0 where there are atleast 2 ones. 1 ones are alread Suppose a is the first one n-1 = 0…0edcb01…1 n & n-1 = 0…0edcba0…0 0…0edcb01…1 = 0…0edcb0000 !=0 because there’s at least a 1 Doesn’t work on any even numbers which is not a square Proved Q.E.D
- For situations where the i is unknown, do manipulations like -1, +1, *-1. Compare with n.