Last Updated: 22 Nov, 2020
Power of Two
Easy
Asked in companies
You have been given an integer 'N'.
Your task is to return true if it is a power of two. Otherwise, return false.
An integer 'N' is a power of two, if it can be expressed as 2 ^ 'K' where 'K' is an integer.
For example:
'N' = 4,
4 can be represented as 2^2. So, 4 is the power of two, and hence true is our answer.
Input Format:
The only line contains an integer 'N'.
Output Format:
The only line contains "true" if the integer 'N' is a power of 2 otherwise "false".
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
Recursive approach is to keep dividing the number by two, i.e. do ‘N’ = ‘N’/2 recursively. In any case, 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.
The idea here 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.
The basic idea is to use Bit Manipulation. 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 becomes unset.
For example for 4 (100) and 16 (10000), we get the following after subtracting 1
3 -> 011
15 -> 01111
So, if a number ‘N’ is 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 the 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)).