Practice › Bit Manipulation
Power of Two
Easy · Bit Manipulation · Asked at Amazon, Google, TCS, Infosys
Print YES if n is a power of two, otherwise NO.
Input
One integer n.
Output
YES or NO.
Constraints
- -10^18 ≤ n ≤ 10^18
A positive n is a power of two exactly when
n & (n − 1) == 0.
Example 1
Input
16
Output
YES
Example 2
Input
6
Output
NO
Hints
- A power of two has exactly one 1 bit in binary (1, 10, 100, …).
- For n > 0, n & (n − 1) == 0 exactly when n has a single set bit. Zero and negatives are never powers of two.
Approach
Clearing the lowest set bit of a power of two leaves 0, and for any other positive number it leaves something non-zero. So the test is n > 0 && (n & (n − 1)) == 0. The n > 0 check matters: 0 passes the bit test, and negative numbers in two's complement can behave unexpectedly.
Complexity: O(1) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
cout << (n > 0 && (n & (n - 1)) == 0 ? "YES" : "NO") << "\n";
return 0;
}Python solution
n = int(input())
print("YES" if n > 0 and n & (n - 1) == 0 else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
System.out.println(n > 0 && (n & (n - 1)) == 0 ? "YES" : "NO");
}
}