Given an integer n, return *true if it is a power of two. Otherwise, return false*.
An integer n is a power of two, if there exists an integer x such that n == 2x.
Example 1:
Input: n = 1
Output: true
Explanation:20 = 1
Example 2:
Input: n = 16
Output: true
Explanation:24 = 16
Example 3:
Input: n = 3
Output: false
Constraints:
231 <= n <= 231 - 1You can use logarithms to solve this problem.
$$ n = 2^x \quad \Longleftrightarrow \quad \log_{2} n = x $$
With this in mind, we can then come up with the solution below:
public class Solution {
public bool IsPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
double logarit = Math.Log(n, 2);
return Math.Abs(logarit - Math.Round(logarit)) < 1e-10;
}
}
First, we reject all n that are zero or negative. Then, we find the log base 2 of n and round the exponent to the nearest whole number. Next, we’re going to check if the real exponent and the rounded one differ by almost nothing. If it is less then 1e - 10, then n is a power of 2.
Nevertheless, you should be cautious when doing it like this, as floating-point numbers can have rounding errors for large values of n. That’s why in competitive programming or coding interviews, the bitwise method below is preferred. It’s much more precise and much faster
In a bitwise operation, a positive integer is a power of two if and only if it has exactly one bit set in its binary representation. Which means that the AND operator of n and n - 1 will be 0.