Given an integer how do we check if it is a power of 2?

For example 1, 2, 4, 8, 16, 32, 64, 128, 256,... are integral powers of 2.

There are several methods to check if a number is a power of 2.

If you repeatedly divide the number by 2 (without any remainder), You will finally get a 1 if it is a power of two.

For example if the number is 64

64/2 = 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1

If the number is 22

22/2 = 11/2 = 5 (we stop here as there is a non-zero remainder)

If you consider the binary representation of the numbers, The powers of 2 always contain just one set (1) bit.

For example

1 = 0000 0001

2 = 0000 0010

4 = 0000 0100

8 = 0000 1000

16 = 0001 0000

...

So by counting the number of set bits and checking if it is 1, we can conclude that it is a power of 2

Please check my previous post for counting the set bits in a number.

This method is also based on an observation of binary representation of numbers.

We all know the Bit-wise and (&) operation . If it is represented by the following table

A B A&B

--------------

1 1 1

1 0 0

0 1 0

0 0 0

If the number n is a power of 2, then the bit-wise and operation between n and (n-1) is always 0.

For N = 64 0100 0000 = 64

0011 1111 = 63

------------- &

0000 0000

For example 1, 2, 4, 8, 16, 32, 64, 128, 256,... are integral powers of 2.

There are several methods to check if a number is a power of 2.

**Method#1: Using repeated division**If you repeatedly divide the number by 2 (without any remainder), You will finally get a 1 if it is a power of two.

For example if the number is 64

64/2 = 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1

If the number is 22

22/2 = 11/2 = 5 (we stop here as there is a non-zero remainder)

public static boolean isPowerOfTwo(int num) { if( num <= 0 ) return false; while( num > 1) { if( num %2 != 0) return false; num = num/2; } return true; }

**Method#2: Counting the set bits**If you consider the binary representation of the numbers, The powers of 2 always contain just one set (1) bit.

For example

1 = 0000 0001

2 = 0000 0010

4 = 0000 0100

8 = 0000 1000

16 = 0001 0000

...

So by counting the number of set bits and checking if it is 1, we can conclude that it is a power of 2

Please check my previous post for counting the set bits in a number.

**Method#3: Efficient and clever**This method is also based on an observation of binary representation of numbers.

We all know the Bit-wise and (&) operation . If it is represented by the following table

A B A&B

--------------

1 1 1

1 0 0

0 1 0

0 0 0

If the number n is a power of 2, then the bit-wise and operation between n and (n-1) is always 0.

For N = 64 0100 0000 = 64

0011 1111 = 63

------------- &

0000 0000

public static boolean isPowerOfTwo(int num) { if( num <= 0 ) return false; return (num & (num-1)) == 0? true: false; }