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.

**Sample Input**

4

**Sample Output **

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; }

**Output**

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; }

**Output**

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.