Check if a number is a power of 4 or not
Given a positive number, check if it is a power of four or not.
Approach 1
A simple solution is to calculate log4n for a given number n. If it returns an integral value, then we can say that the number is a power of four.
This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <cmath> using namespace std; // Returns true if `n` is a power of four bool checkPowerOf4(unsigned n) { // find `log4(n)` double i = log(n) / log(4); // return true if `log4(n)` is an integer return i == trunc(i); } int main() { unsigned n = 256; if (checkPowerOf4(n)) { cout << n << " is a power of 4"; } else { cout << n << " is not a power of 4"; } return 0; } |
Output:
256 is a power of 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { // Returns true if `n` is a power of four public static boolean checkPowerOf4(int n) { // find `log4(n)` double i = Math.log(n) / Math.log(4); // return true if `log4(n)` is an integer return i == Math.floor(i); } public static void main(String[] args) { int n = 256; if (checkPowerOf4(n)) { System.out.println(n + " is a power of 4"); } else { System.out.println(n + " is not a power of 4"); } } } |
Output:
256 is a power of 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from math import log, floor # Returns true if `n` is a power of four def checkPowerOf4(n): # find `log4(n)` i = log(n) / log(4) # return true if `log4(n)` is an integer return i == floor(i) if __name__ == '__main__': n = 256 if checkPowerOf4(n): print(n, 'is a power of 4') else: print(n, 'is not a power of 4') |
Output:
256 is a power of 4
Approach 2
The given number n is a power of 4 if it is a power of 2 and its only set bit is present at even position (0, 2, 4, …).
How to check for power of 2?
The expression n & (n-1) will unset the rightmost set bit of a number. If the number is a power of 2, it has only a 1–bit set, and n & (n-1) will unset the only set bit. So, we can say that n & (n-1) returns 0 if n is a power of 2; otherwise, it’s not a power of 2.
We can also the expression (n & -n) == n to check if a positive integer is a power of 2 or not. For more details, refer to this post.
How to check position of the set bit?
To check the position of its set bit, we can use 0xAAAAAAAA as a mask. The mask 0xAAAAAAAA has 1 in all its odd position. So if the expression !(n & 0xAAAAAAAA) is true, the position of the set bit in n is even.
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; // Returns true if `n` is a power of four bool checkPowerOf4(unsigned n) { // return true if `n` is a power of 2, and its only // set bit is present at even position return n && !(n & (n - 1)) && !(n & 0xAAAAAAAA); } int main() { unsigned n = 256; if (checkPowerOf4(n)) { cout << n << " is a power of 4"; } else { cout << n << " is not a power of 4"; } return 0; } |
Output:
256 is a power of 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { // Returns true if `n` is a power of four public static boolean checkPowerOf4(int n) { // return true if `n` is a power of 2, and its only // set bit is present at even position return n != 0 && (n & (n - 1)) == 0 && (n & 0xAAAAAAAA) == 0; } public static void main(String[] args) { int n = 256; if (checkPowerOf4(n)) { System.out.println(n + " is a power of 4"); } else { System.out.println(n + " is not a power of 4"); } } } |
Output:
256 is a power of 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Returns true if `n` is a power of four def checkPowerOf4(n): # return true if `n` is a power of 2, and its only # set bit is present at even position return n and not (n & (n - 1)) and not (n & 0xAAAAAAAA) if __name__ == '__main__': n = 256 if checkPowerOf4(n): print(n, 'is a power of 4') else: print(n, 'is not a power of 4') |
Output:
256 is a power of 4
Approach 3
The given number n is a power of 4 if it is a power of 2 and its remainder is 1 when it is divided by 3. This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; // Returns true if `n` is a power of four bool checkPowerOf4(unsigned n) { // return true if `n` is a power of 2, and // the remainder is 1 when divided by 3 return !(n & (n - 1))&& (n % 3 == 1); } int main() { unsigned n = 256; if (checkPowerOf4(n)) { cout << n << " is a power of 4"; } else { cout << n << " is not a power of 4"; } return 0; } |
Output:
256 is a power of 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { // Returns true if `n` is a power of four public static boolean checkPowerOf4(int n) { // return true if `n` is a power of 2, and // the remainder is 1 when divided by 3 return ((n & (n - 1)) == 0) && (n % 3 == 1); } public static void main(String[] args) { int n = 256; if (checkPowerOf4(n)) { System.out.println(n + " is a power of 4"); } else { System.out.println(n + " is not a power of 4"); } } } |
Output:
256 is a power of 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Returns true if `n` is a power of four def checkPowerOf4(n): # return true if `n` is a power of 2, and # the remainder is 1 when divided by 3 return ((n & (n - 1)) == 0) and (n % 3 == 1) if __name__ == '__main__': n = 256 if checkPowerOf4(n): print(n, 'is a power of 4') else: print(n, 'is not a power of 4') |
Output:
256 is a power of 4
Exercise: Check if the number is a power of 8 or 16 or not
(Hint – Check the bit pattern. Use mask 0xB6DB6DB6 to check for power of 8 and 0xEEEEEEEE for power of 16)
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)