Power of Two Check

Problem

Read an integer n (|n| < 2^31). Print true if n is a power of two (1, 2, 4, 8, ...), else false.

Constraints

  • -2^31 < n < 2^31

Examples

Input

16

Output

true

Solutions

Best approachTime O(1)Space O(1)

In binary, a power of two looks like 1000. Subtract 1 and you get 0111. The AND of both is 0.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Check if a number is a power of two.
 * Input   : One integer.
 * Output  : true or false.
 * Approach: A power of two has one set bit.
 * Time    : O(1)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(long n) {
        // Step 1: A power of two must be positive.
        // Step 2: A power of two has exactly one bit set, so n & (n - 1) removes it and leaves 0.
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. Write 8 and 7 in binary.