Check whether a Number is a Power of 4 or Not in Java
There are many ways to figure out if an integer is a power of 4. This section will go over a variety of techniques for figuring out whether or not a number is a power of four.
Examples:
Input: n = 9
Result: 9 is not pow of 4
Input: n = 14
Result: 12 is not pow of 4.
Input: n = 16
Result: 16 is pow of 4. 4^2 = 16
Approach: Using log base 4 with ceil and floor
Using this method, we calculate the input number's log4 value. J is a number that is a power of 4 if the result of the log4(j), where j is the input number, is an integer; otherwise, it is not.
// java program
public class NPF
{
// a technique that determines whether or not y is a power of 4 public booleanisPOF(int j)
{
double db = (Math.log(j) / Math.log(4));
booleanisPow = Math.ceil(db) == Math.floor(db);
return isPow;
}
// main method
public static void main(String argvs[])
{
// building a NumPowFour class object
NPF ob = new NPF();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16; if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four
Checking for power of 2
The rightmost set bit of a number will be unset by the formula a& (a-1). a& (a-1) will unset the only set bit if the number is a power of 2, which only has one bit set. Therefore, we can state that a& (a-1) returns 0 if n is a power of 2 and returns nonzero otherwise.
To determine if a positive integer is a power of two or not, we may alternatively use the phrase (a& -a) == a.
Approach: Using log base 4 without ceil and floor
Using this method, we determine the log4 value of the input number (say, the input number is j). Assume that the value is t. As an exponent of the integer 4, or 4(int), we take an integral part of the value. When the value is j, j is a power of four; otherwise, it is not.
// java program
public class NPF1
{
// a technique that determines whether or not y is a power of 4 public booleanisPOF(int j)
{
return (j> 0 &&Math.pow(
4, (int)(Math.log(j) / Math.log(4) )) == j);
}
// main method
public static void main(String argvs[])
{
// building a NPF1 class object NPF1 ob = new NPF1();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four
Approach: Divide by 4
Step 1: determine whether the inputted integer is divisible by 4 or not. The input number is not a power of four if it is not divisible.
Step 2: Multiply the number by 4 if it is divisible. The input number is a power of 4 if the result of division is 1, which is the case. Repeat steps 1 and 2 if the obtained number is not 1.
Let's observe how it is put into practice.
public class NPF2
{
// a technique that determines whether or not y is a power of 4 public booleanisPOF(int j)
{
do
{
if(j == 1)
{
return true;
}
else if(j % 4 == 0)
{ j = j / 4;
} else
{
return false;
}
}while(true);
}
// main method
public static void main(String argvs[])
{
// building a NPF2 class object
NPF2 ob = new NPF2();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256; if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8; if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16; if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four
Approach: Set bit
Any number that is a power of two shares the property of having only one set bit in its binary form. Look at the table below.
Number | Binary representation |
1 | 1 |
2 | 10 |
3 | 11 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
8 | 1000 |
9 | 1001 |
10 | 1010 |
The numerals 1, 2, 4, and 8 have only one bit set. All of these numbers are powers of 2, with 20 being a 1, 21 being a 2, 22 being a 4, and 23 being an 8.
The properties of a number that is a power of four are as follows:
Since a power 4 number is always a power 2 number, there is only one bit set in that number.
It must be an even number of zeros after the set bit. In binary, 2 equals 10, and the number of zeros following the set bit is 1, which is strange. As a result, 2 is not a power of 4. The binary representation of 16 is 10000, and the even number of zeros following the set bit is 4, making a total of 16. 16 is therefore a power of four.
The software that follows will use the qualities listed above to determine the numbers that are powers of 4.
// java program
public class NPF3
{
// a procedure that determines whether or not j is a power of 4
public booleanisPOF(int j)
{
// for checking only one bit is set or not
if((j& (j - 1)) == 0)
{
int countZ = 0;
// loop for count the zeros after the set bit
while((j& 1) == 0)
{
countZ = countZ + 1;
// shifting the bit by 1;
j = j>> 1;
}
// determining whether or if there are even or odd numbers of zeros after the set bit
return (countZ % 2 == 0) ? true : false;
}
// reaching here indicates that there are several set bits, hence the number cannot be a power of 4.
return false;
}
// main method
public static void main(String argvs[])
{
// building a NPF3 class object
NPF3 ob = new NPF3();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four
It is also possible to perform the & operation using 0xAAAAAAAA instead of counting zeros after the set bit. It's crucial to use the & operation with the value 0xAAAAAAAA because it eliminates any values with an odd number of zeros after the set bit (2, 8, 32, etc.). Take note of the program below.
// java program
public class NPF4
{
// a procedure that determines whether or not j is a power of 4
public booleanisPOF(int j)
{
// for checking only one bit is set or not
if((j& (j - 1)) == 0)
{
// removing any powers of two that are not powers of four Example: 2, 8, 32, etc.
return ((j& 0xAAAAAAAA) == 0) ? true : false;
}
// reaching here indicates that there are several set bits, hence the number cannot be a power of 4.
return false;
}
// main method
public static void main(String argvs[])
{
// building a NPF4 class object
NPF4 ob = new NPF4();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four
Approach: Perfect Square
Any integer that is a power of 4, since 4 is a perfect square, must also be a perfect square. The two factors listed below are sufficient to determine whether a number is a power of four or not.
The quantity must be a power of two.
The quantity must be an exact square.
// java program
public class NPF5
{
// a procedure to determine whether or not the integer j is a perfect square.
public booleaniPSqr(int j)
{
int ps = (int) Math.sqrt(j);
return ((ps * ps) == j);
}
// a procedure to determine whether or not the integer j is a perfect square.
public booleanisPOF(int j)
{
int nu = 2;
if(iPSqr(j))
{
// Check to see whether an integer is a power of two if it is a perfect square.
while(true)
{
if(nu == j)
{
return true;
}
else if ( nu >j)
{
return false;
}
nu = nu* 2;
}
}
// reaching here indicates that the number is not a perfect square, hence it cannot be a power of four.
return false;
}
// main method
public static void main(String argvs[])
{
// building a NPF5 class object
NPF5 obj = new NPF5();
int a2 = 17;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 256;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 8;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
a2 = 16;
if(ob.isPOF(a2))
{
System.out.println(a2 + " is pow of four. ");
}
else
{
System.out.println(a2 + " is not pow four. ");
}
}
}
Output:
17 is not pow four.
256 is pow of four.
8 is not pow four.
16 is pow of four.