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
In binary, a power of two looks like 1000. Subtract 1 and you get 0111. The AND of both is 0.
/*
* 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)
- Write 8 and 7 in binary.