Given a number, check if it is power of four or not.

##### Approach 1:

A simple solution would be to calculate log_{4}n for given number n. If it returns an integral value, then we can say that the number is power of four.

**C++ implementation –**

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 |
#include <iostream> #include <math.h> using namespace std; // returns true if n is 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); } // main function int main() { unsigned n = 256; if (checkPowerof4(n)) cout << n << " is power of 4"; else cout << n << " is not a power of 4"; return 0; } |

`Output:`

256 is power of 4

##### Approach 2:

The given number n is power of 4 if it is 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 power of 2, it has only one 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 power of 2 else it is 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, please refer this post.

**How to check position of set bit ?**

Simple. 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, position of set bit in n is even.

(0xAAAAAAAA)_{16} = (10101010101010101010101010101010)_{2}

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; // returns true if n is power of four bool checkPowerof4(unsigned n) { // return true if n is power of 2 and its only // set bit is present at even position return n && !(n & (n - 1)) && !(n & 0xAAAAAAAA); } // main function int main() { unsigned n = 256; if (checkPowerof4(n)) cout << n << " is power of 4"; else cout << n << " is not a power of 4"; return 0; } |

`Output:`

256 is power of 4

##### Approach 3:

The given number n is power of 4 if it is power of 2 and its remainder is 1 when it is divided by 3.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; // returns true if n is power of four bool checkPowerof4(unsigned n) { // return true if n is power of 2 and // remainder is 1 when it is divided by 3 return !(n & (n - 1))&& (n % 3 == 1); } // main function int main() { unsigned n = 256; if (checkPowerof4(n)) cout << n << " is power of 4"; else cout << n << " is not a power of 4"; return 0; } |

`Output:`

256 is power of 4

**Exercise:** Check if number is power of 8 or 16 or not

(Hint – Check the bit pattern. Use 0xB6DB6DB6 mask to check for Power of 8 and 0xEEEEEEEE for Power of 16)

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply