# Power of Two

Difficulty Level Easy
Frequently asked in Apple
Bit Bit Manipulation Bits MathViews 815

In Power of Two problem we have given an integer, check if it is the power of 2 or not. A number in the power of two if it has only one set bit in the binary representation. Let’s see one example of a number that contains only one set bit. If our input is 16 then we can represent it in binary format like 10000. Here we see that only one bit is 1 which means the number represents in the power of 2. Now see one example in which a set bit is more than 1. If our input is 13 then we represent it in binary format like 1101. Here we see there are 3 set bits. So we can’t represent it in the form of 2^y where y is an integer greater than 0.

## Input Format

First-line containing an integer value N.

## Output Format

Print “true” if we represent it in a given format else print “false”.

## Constraints

• 1<=N<=10^18.

4

true

### Explanation

We know that already the binary representation of 4 is 100 which means only one set bit here. So we represent it in form 2^y(2^2).

## Iterative approach

• Negative numbers and zero can never be in form 2^y where y is an integer.
• check if n can be divided by 2. If yes, divide n by 2 and check it repeatedly.
• if at last n is reduced to 1 then n is a power of 2 else it is not the form 2^y where y is an integer.

## Implementation

### C++ Program for Power of Two

```#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n%2 == 0) n/=2;
return n == 1;
}
int main()
{
int n=4;
int ans=isPowerOfTwo(n);
if(ans)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}```

`true`

### Java Program for Power of Two

```public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n%2 == 0) n/=2;
return n == 1;
}```

### Time complexity

O(log n) because at each step we are dividing the number by 2.

## Bit operation approach

• Negative numbers and zero can never be a power of 2.
•  If a number is power of 2 then ( n & (n-1) )==0

## Implementation

### C++ Program for Power of Two

```#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
return (n > 0 && (n & (n-1)) == 0);
}
int main()
{
int n=4;
int ans=isPowerOfTwo(n);
if(ans)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}```

`true`

### Java Program for Power of Two

``` public boolean isPowerOfTwo(int n) {
return (n>0&&(n & (n-1))==0);
}```

### Time Complexity

O(1) because using only single AND we can find whether the number satisfies the condition or not.

References

Translate »