How to solve the power of four problem using bits in Java

In this shot, we will learn how to determine whether a number is a power of 4.

Example

Let’s understand with the help of two examples.

  • Suppose the number is 16. As 16 = 4^2, our solution should tell the user that 16 is a power of 4.

  • Now, suppose that the number is 18. As 18 is not equal to 4^n for any integral value of n, our solution should tell the user that 18 is not a power of 4.

Solution approach

To solve this problem, we will perform a bit of manipulation. We will use the bit power of 2 and remainder on division by 3 to determine whether a number is a power of 4 or not. The time complexity and space complexity for this case is O(1).

Code

Let’s have a look at the code.

import java.util.*;
class Main
{
    public static void main(String[] args) 
    {
        int n = 16;
        int x = n;
        if (n == 0)
            System.out.println(x + " is not the power of 4");
                
        else {
            boolean res = (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
            if(res) 
                System.out.println(x + " is the power of 4");
            else
                System.out.println(x + " is not the power of 4");
        }
    }
}

Explanation

  • In line 1, we import the required package.

  • In line 2, we make a Main class.

  • In line 4, we make a main() function.

  • In line 6, we define the number that we want to check.

  • In line 7, we store the value of that number in a separate variable, as the original variable’s value may change when we perform the bit operations.

  • In lines 9 and 10, we have an if statement to check whether the number is positive or not, and if not, a message is displayed.

  • We know that the power of 4 will also be an even power of 2, so we check whether the given number is a power of 2 or not and the number on division with 3 gives remainder 1, then it is a power of 4, otherwise not. We store the result of this in a boolean type variable.

  • In lines 14 to 17, we use an if - else statement to check whether the result value is true, i.e., the number is a power of 4 or the result value is false, i.e., the number is not a power of 4, and display the result accordingly.

In this way, we can solve the Power of Four problem in Java using bit manipulation.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)