How to solve the power of four problem using bits in Java
Harsh JainIn 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
Mainclass. -
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
ifstatement 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
booleantype variable. -
In lines 14 to 17, we use an
if - elsestatement to check whether the result value istrue, i.e., the number is a power of 4 or the result value isfalse, 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
CONTRIBUTOR
Harsh JainView all Courses
