Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A power of two has exactly one 1 bit in binary (1, 10, 100, …).
  2. 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");
    }
}

Solve Power of Two online · All practice problems