Determining if a number is a power of 2 is a common problem in computer science and programming. A number is considered a power of 2 if it can be expressed as 2^n, where n is a non-negative integer. For example, the numbers 1, 2, 4, 8, 16, and so on are all powers of 2.
In this post, we will explore two approaches to solve this problem: the normal approach and the bitwise approach.
Problem: Given an integer n, determine whether it is a power of two.
Example:
Input: 8
Output: true
Explanation: 8 = 2^3 → It is a power of 2
Input: 6
Output: false
Explanation: 6 is not a power of 2Approach 1: Brute Force Loop.
Keep dividing the number by 2. If at the end, you reach 1, then it's a power of 2.
If at any point, it's not divisible by 2, return false.
Steps:
- If n == 0, return false
- While n % 2 == 0, divide n by 2
- If n == 1 after loop → power of 2
Example Code:
// C++ Example: Find Power of 2
#include <iostream>
using namespace std;
bool isPowerOfTwoLoop(int n) {
if (n <= 0) return false;
while (n % 2 == 0) {
n = n / 2;
}
return n == 1;
}
int main() {
int number;
cout << "Enter a number: ";
cin >> number;
if (isPowerOfTwoLoop(number)) {
cout << number << " is a power of 2." << endl;
} else {
cout << number << " is not a power of 2." << endl;
}
return 0;
}
8 is a power of 2.
- Time Complexity: O(log n)
- Space Complexity: O(1)
Approach 2: Bit Manipulation Approach.
A number is a power of two if it can be expressed as 2^n, where n is a non-negative integer. In binary representation, powers of two have a unique property: they have exactly one bit set to 1.
For example:
1 = 0001 → 2^0
2 = 0010 → 2^1
4 = 0100 → 2^2
8 = 1000 → 2^3
16 = 10000 → 2^4
This property allows us to efficiently check if a number is a power of two using bit manipulation.
To determine if a number n is a power of two using bit manipulation, we can use the following approach:
1. Check if n is greater than zero: Powers of two are positive numbers.
2. Use the expression (n&(n-1): This expression will be zero if n is a power of two. The reason behind this is that subtracting 1 from a power of two flips all the bits after the rightmost set bit (the only 1 in the binary representation). For example:
- For n = 4 (0100), n-1 = 3 (0011)
- The bitwise AND operation: 0100 & 0011 = 0000
Now, let's implement this logic in C++, Python, and Java.
Example Code:
#include <iostream>
bool isPowerOfTwo(int n) {
return (n > 0) && ((n & (n - 1)) == 0);
}
int main() {
int number = 8;
if (isPowerOfTwo(number)) {
std::cout << number << " is a power of two." << std::endl;
} else {
std::cout << number << " is not a power of two." << std::endl;
}
return 0;
}
8 is a power of two.
- Time Complexity: O(l)
- Space Complexity: O(1)
