Understanding the Problem
We are given a positive integer n
, and we need to determine if it is a power of two.
A number is considered a power of two if it can be written as 2k
where k
is a non-negative integer. Examples include: 1, 2, 4, 8, 16, 32, and so on.
The key observation is that powers of two have exactly one bit set in their binary representation. For example:
- 1 =
0001
- 2 =
0010
- 4 =
0100
- 8 =
1000
If a number has only one bit set, then n & (n - 1)
will be 0
.
Step-by-Step Solution with Example
step 1: Understand what input we are working with
Suppose we are given n = 8
.
The binary representation of 8
is 1000
, which clearly has only one bit set.
step 2: Check if the number is greater than 0
We start by checking if n > 0
. If it's not, we return false
immediately because negative numbers and zero cannot be powers of two.
Here, 8 > 0
, so we proceed to the next step.
step 3: Apply the bitwise trick n & (n - 1)
Let’s compute n - 1
which is 7
. In binary, that’s 0111
.
Now compute 8 & 7
:
1000 (8)
& 0111 (7)
----
0000
Since the result is 0
, this means n
is a power of two.
step 4: Return true if result is 0, otherwise false
Because we got 0
from the bitwise AND, we return true
.
Edge Cases
- n = 0: Not a power of two. Return
false
.
- n = 1: Considered a power of two (
20
). Return true
.
- n = -8: Negative numbers can never be powers of two. Return
false
.
- n = 18: Binary is
10010
, which has more than one bit set. Return false
.
Final Thoughts
This approach is highly efficient because it uses bitwise operations, which are fast and require only constant time.
For beginners, remember: the trick n & (n - 1)
helps you check if there's only one bit set. That’s the magic behind detecting powers of two!
Always start with validating the input, especially for 0 and negative numbers.
Comments
Loading comments...