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 Bitwise 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)

---

 
package javabypatel;

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)

---

package javabypatel;

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. 

You may also like to see

---

Place N Queens on N×N chess board such that no two Queens attack each other.

0/1 Knapsack Problem solved using Iterative and Dynamic Programming

Stock Buy Sell to Maximize Profit.

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted

Count trailing zeros in factorial of a number.

How to Detect loop in linked list.

Tower Of Hanoi Program in Java.

Print Matrix Diagonally OR Diagonal order of Matrix.

Transpose of Matrix Inplace

Implement Queue using One Stack in Java (Recursive Implementation)

SOAP Vs REST Web Service, when to use SOAP, When to use REST.

Enjoy !!!! 

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