Check if given number is power of 8 or not

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

 

Approach 1 –

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

C++

Download   Run Code

Output:

32768 is power of 8

Approach 2 –

The given number n is power of 8 if it is power of 2 and its only set bit is present at
(0, 3, 6, . . .30) position.

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 refer this post.

How to check position of set bit ?

To check the position of its set bit we can use 0xB6DB6DB6 as a mask. The mask 0xB6DB6DB6 has 0 in all (0, 3, 6, . . .30) position. So if the expression !(n & 0xB6DB6DB6) is true, position of set bit in n is even.

(0xB6DB6DB6)16 = (10110110110110110110110110110110)2

C++

Download   Run Code

Output:

256 is power of 8

 
Exercise: Check if number is power of 4 or 16 or not

(Hint – Check the bit pattern)
Use 0xAAAAAAAA mask to check for Power of 4
Use 0xEEEEEEEE mask to check 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