Check if given number is power of 4 or not

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

 

Approach 1:

 

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

 
C++ implementation –
 

Download   Run Code

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 –
 

Download   Run Code

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 –
 

Download   Run Code

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of