Given a positive integer, write a function to find if it is a power of two or not.
Examples:
Input : n = 4 Output : Yes 22 = 4 Input : n = 7 Output : No Input : n = 32 Output : Yes 25 = 32[ad type=”banner”]
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
1. A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.
2. Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23define%20bool%20int%0A%20%0A%2F*%20Function%20to%20check%20if%20x%20is%20power%20of%202*%2F%0Abool%20isPowerOfTwo(int%20n)%0A%7B%0A%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20return%200%3B%0A%20%20while%20(n%20!%3D%201)%0A%20%20%7B%0A%20%20%20%20if%20(n%252%20!%3D%200)%0A%20%20%20%20%20%20return%200%3B%0A%20%20%20%20n%20%3D%20n%2F2%3B%0A%20%20%7D%0A%20%20return%201%3B%0A%7D%0A%20%0A%2F*Driver%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20isPowerOfTwo(31)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20isPowerOfTwo(17)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20isPowerOfTwo(16)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20isPowerOfTwo(2)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20isPowerOfTwo(18)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20isPowerOfTwo(1)%3F%20printf(%22Yes%5Cn%22)%3A%20printf(%22No%5Cn%22)%3B%0A%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]Output:
No No Yes Yes No Yes
3. All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. Please see http://www.geeksforgeeks.org/?p=1176 for counting set bits.
4. If we subtract a power of 2 numbers by 1 then all unset bits after the only set bit become set; and the set bit become unset.
For example for 4 ( 100) and 16(10000), we get following after subtracting 1
3 –> 011
15 –> 01111
So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become n& (!n&(n-1)) (thanks to Mohammad for adding this case).
Below is the implementation of this method.
Output:
No No Yes Yes No Yes[ad type=”banner”]