In this shot, we will learn how to determine whether a number is a power of 4.
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.
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).
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"); } } }
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
CONTRIBUTOR
View all Courses