## 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