Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java
communitycreator

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

Harsh Jain

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");
        }
    }
}
Solution of the Power of Four problem

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.

RELATED TAGS

java
communitycreator
RELATED COURSES

View all Courses

Keep Exploring