How to check if an integer number is a power of 2 in Java is one of the popular programming interview questions and has been asked in many interviews. Surprisingly, this problem which looks simple enough to answer doesn't turn out that simple if for many developers. Many Java programmers, both freshers and less experienced, struggle to write code for a function, which can check if the number is the power of 2 or not.
There could be many different reasons for that, but it’s expected to at least come up with a brute force solution. For those who are familiar with bitwise operators in Java, how positive and negative numbers are represented in binary format, this exercise is quite easy.
Since negative numbers are represented as 2's complement value in Java, you can easily find if any number is the power of 2 or not by looking at its bit pattern.
Remember checking for the power of two is different than checking if a number is even or odd, that’s another thing to note.
A number can be even, but it’s not necessary to be a power of two, like 6 is even but it’s not a power of two.
3 ways to check if a number is the power of two or not
In this article, we will see 3 simple examples to check if an integer number is a power of 2 or not. We have three methods, which use bitwise operator, brute force way, and bit shit operators to solve this problem. The method which uses bitwise operators can not check if zero is the power of 2 or not, and only work for integer number which is greater than or equal to 1. here is a code example of 3 simple methods to find out if a number is the power of 2 or not :
public class PowerOf2Test {
public static void main(String args[]) {
int[] numbers = {0,1,2,6,8};
for(int num: numbers){
System.out.println("isPowerOfTwo()-- is " + num + " power of two in Java :" + isPowerOfTwo(num));
System.out.println("powerOfTwo()-- is " + num + " power of two in Java :" + powerOfTwo(num));
System.out.println("checkPowerOfTwo()-- is " + num + " power of two in Java :" + checkPowerOfTwo(num));
System.out.println("-----------------------------------------------------------");
}
}
/*
* checking if number is power of 2 using bit shift operator in java
* e.g. 4 in binary format is "0000 0000 0000 0000 0000 0000 0000 0100";
* and -4 is "1111 1111 1111 1111 1111 1111 1111 1100";
* and 4&-4 will be "0000 0000 0000 0000 0000 0000 0000 0100"
*/
private static boolean isPowerOfTwo(int number) {
if(number <0){
throw new IllegalArgumentException("number: " + number);
}
if ((number & -number) == number) {
return true;
}
return false;
}
/*
* checking if number is power of 2 using brute force
* starts with 1, multiplying with 2 it will eventually be same as original number
*/
private static boolean powerOfTwo(int number){
int square = 1;
while(number >= square){
if(number == square){
return true;
}
square = square*2;
}
return false;
}
/*
* find if an integer number is power of 2 or not using bit shift operator
*/
private static boolean checkPowerOfTwo(int number){
if(number <0){
throw new IllegalArgumentException("number: " + number);
}
return ((number & (number -1)) == 0);
}
}
Output:
isPowerOfTwo()-- is 0 power of two in Java :true
powerOfTwo()-- is 0 power of two in Java :false
checkPowerOfTwo()-- is 0 power of two in Java :true
-----------------------------------------------------------
isPowerOfTwo()-- is 1 power of two in Java :true
powerOfTwo()-- is 1 power of two in Java :true
checkPowerOfTwo()-- is 1 power of two in Java :true
-----------------------------------------------------------
isPowerOfTwo()-- is 2 power of two in Java :true
powerOfTwo()-- is 2 power of two in Java :true
checkPowerOfTwo()-- is 2 power of two in Java :true
-----------------------------------------------------------
isPowerOfTwo()-- is 6 power of two in Java :false
powerOfTwo()-- is 6 power of two in Java :false
checkPowerOfTwo()-- is 6 power of two in Java :false
-----------------------------------------------------------
isPowerOfTwo()-- is 8 power of two in Java :true
powerOfTwo()-- is 8 power of two in Java :true
checkPowerOfTwo()-- is 8 power of two in Java :true
-----------------------------------------------------------
That’s all on this article about checking if a number I power of two or not. In this article, I have showed you 3 different ways to check if a given number is power of two or not, the brute force way which keep increasing power of 2 until it reaches the number of two bit shift way which is used to check if the number if power of two or not. Let us know if you find another way to verify if the number is the power of two.
Related Java Coding Questions from Javarevisited Blog
Now is the quiz time, which one is your favorite way to check if the number if power of two or not? By using brute force way using multiplication or division operator or by using bitwise and bit shift operator in Java?
Is the brute force case, O(logN) complexity since you are multiplying by 2 each time? So log base 2 of N?
ReplyDeletewhat about this???
ReplyDeletepublic class PowerOftwo
{
public void powerOftwo(int number)
{
int num = number;
int d;
boolean flag = true;
while(num>1)
{
d = num % 2;
if(d%2!=0)
{
flag = false;
break;
}
num = num/2;
}
if(flag == true)
{
System.out.println("Number is a power of 2");
}
else
{
System.out.println("Number is not a power of 2");
}
}
public static void main(String[] args)
{
int number =16;
PowerOftwo obj = new PowerOftwo();
obj.powerOftwo(number);
}
}
Hi...i follow your blog while coding in my office...I really find your site useful...recently i joined your site as I am also creating a blog for technical implementations. Its in a very early stage..
ReplyDeleteProgramming Language http://javacodeimpl.blogspot.in/
I often read, heard that power of 2 numbers have special significance in computer world, Why? Why most HashMap, HashSet use sizes which is power of 2? WHY
ReplyDeletepublic static boolean isPowerOfTwo(int i){
ReplyDeleteif (i==0) return false;
int d = Math.abs(i);
return (d & (d-1)) == 0;
}
You may just use Integer.bitcount(number) == 1
ReplyDeleteWOW, Some clever tips checking integer is power of two, on comments :)
ReplyDeleteTake logs and cast one side as int and check if two sides are equal
ReplyDeletepublic static boolean (int i)
return if((int)(Math.log(i+1)/Math.log(2)) - ((Math.log(i+1)/Math.log(2)))==0)
return x == 0 ? false : x & (x - 1) == 0;
ReplyDeleteIs this possible?
ReplyDeleteclass two
{
public static void power(int num)
{
int dup= num ;
while (dup > 2)
{
if (dup==2)
System.out.print (num+"is a power of two");
else if (dup < 2)
System.out.print(num+"is not a power of two");
dup=dup/2;
}
}
By
Ram
For the first and third method, I think there is a typo:
ReplyDeleteif(number<=0)
how can you display 0? And the result returns true?
@TCool, you are correct, its not <= but just less than, corrected it now
ReplyDeleteComments have a semantic error. Bit shift operators are <<, >>, and >>>. Solutions are using bit AND operator &.
ReplyDeleteyou know, you could've just used modulo on a number by dividing it by 2 (num%2). if it equals to 0, then it's an even/power by 2 ;)
ReplyDelete20 % 2 equals 0, but 20 is not a power of 2.
ReplyDeleteIn the third example (using the bit-shift operator) it checks to see if the number is less than 0 and raises an exception. Why!!
ReplyDeleteIf the number is negative, then it's not a power of two (at least not a rational one), but that doesn't seem a good reason to declare number to be an illegal argument. Since the code already has a test why not test for number being less than 1 and returning false. (I'm pretty sure that 0 is 2 to the power of minus infinity, so I'd say that was out the scope of the question too).
Infinity is not a value.
ReplyDelete@Miguel Duran, Exactly: So if you started with
ReplyDeleteif(number < 1) return false;
That would most likely be just as efficient an algorithm, but it would be more accurate (it would return false for 0) and it would be more orthogonal in the sense that it would return a consistent and correct answer over a wider range of input, rather than arbitrarily raising an exception.