Check if number is Power of Two.

Check if number is power of 2.

Lets understand what is the input and the expected output.

If the number given to you is,

Case 1:
Number = 8
8 is power of 2 because 2^3 is 8

Case 2:
Number = 9
9 is not power of 2 because 2^3 is 8 and next number 2^4 is 16, So 9 will not fall in powers of 2.

For better understand check the Value column in above image, it contains powers of 2 till 128.

1(2^0) , 2(2^1), 4(2^2), 8(2^3), 16(2^4).... are all powers of 2

Algorithm

For identifying whether the given number is power of 2, there are many approaches,

Approach 1

In this simple approach,

STEP 1. Check if a number is perfectly divisible by 2 by doing (number % 2). If the number is
               perfectly divisible by 2 then remainder is 0.

STEP 2. If the number is NOT perfectly divisible by 2 then remainder is not 0 and return from here
               as number is not power of 2.

               If the number is perfectly divisible by 2 then remainder is 0 and check whether the
               remaining number (number / 2) is perfectly divisible by 2.

STEP 3. Repeat the steps until the number is 1.

This method requires O(log N) time complexity.

Approach 2

In this approach, We will use Bit manipulation.

Number which are power of 2 like 4, 8, 16, 32 etc has only one bit set in there binary representation.

and number which are one less like 3, 7, 15, 31 etc has all the bits set in there binary representation apart from bit set in 4, 8, 16, 32.

1 0 0 0 0 (16) n
& 0 1 1 1 1 (15) n-1
---------------------------------------
0 0 0 0 0

So if we do logical AND of (number) & (number -1) and if the result is 0 than the number is power of 2 else not.

This method requires O(1) time complexity.

Java Program to check if a given number is power of 2 (Approach 1)

 public class CheckNumberIsPowerOf2 {

 public static void main(String[] args) {
  System.out.println(powerOf2(1));
 }

 private static boolean powerOf2(int number){
  if(number<=0){
   return false;
  }
  
  while(number > 1){
   if(number % 2 != 0){
    return false;
   }
   number = number / 2;
  }
  return true;
 }

}

Java Program to check if a given number is power of 2 (Approach 2)

public class CheckNumberIsPowerOf2 {

 public static void main(String[] args) {
  System.out.println(powerOf2(1));
 }

 private static boolean powerOf2(int number){
     return (number > 0) && ((number & (number - 1)) == 0);
 }
}

(number > 0) is added for the case to check whether entered number is greater than 0. otherwise we have to separately check that condition.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.