Check whether an integer is a power of two

Given a signed 32-bit integer n, return true if n is an exact power of 2, otherwise return false.

A power of 2 is a number of the form 2^k where k >= 0 (e.g., 1, 2, 4, 8, 16, ...).

Input

• n : an integer in the range [-2^31, 2^31 - 1]

Output

• Boolean indicating whether n is a power of 2.

Examples

• n = 1 → true (2^0)
• n = 16 → true (2^4)
• n = 3 → false
• n = 0 → false
• n = -8 → false

Follow-up

• Aim for an O(1) / bit-manipulation solution (no loops over bits, and no precomputed set/table of powers).