Thursday 14 January 2016

How to check the number is power of two?

How to check the number is power of two?

Approach #1:
Divide number by 2 reclusively to check it.
Time complexity : O(log2n).

Approach #2:
Bitwise AND the number with its just previous number should be equal to ZERO.

Example: Number = 8
Binary of 8: 1 0 0 0
Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.
Time complexity : O(1).

Approach #3:
Bitwise XOR the number with its just previous number should be sum of both numbers.

Example: Number = 8
Binary of 8: 1 0 0 0
Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 1 1 1 1 = 15.
Time complexity : O(1).


import java.util.Scanner;
public class PowOfTwo {
      public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int num = scan .nextInt();
            checkUsingANDOperation(num);

            checkUsingXOROperation(num);
            scan.close();
      }

      /**
       * Check Using AND Operation
       */
      private static void checkUsingANDOperation(int num) {
            if((num & (num-1))==0) {
                  System.out.println(num+" is the power of 2");
            } else {
                  System.out.println(num+" is not the power of 2");
            }
      }

      /**
       * Check Using XOR Operation
       */
      private static void checkUsingXOROperation(int num) {
            if((num ^ (num-1))==2*num-1) {
                  System.out.println(num+" is the power of 2");
            } else {
                  System.out.println(num+" is not the power of 2");
            }
      }
}

Output:
8
8 is the power of 2
8 is the power of 2

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...