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 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

Notify of
avatar
wpDiscuz