# The Power Of Two (more than 2^64)

Problem:-
The range of number is greater than long long int that is greater than 2^64.
Therefore each digit of the number is stored in a character array terminating by backslash zero :P(i.e. string terminator ).
How to find out,whether the number is a power of 2 or not?

Solution:-
This problem can be solved with little manipulation through the  Karnaugh Map and truth table.

See carefully the pattern of power of 2 and the number 1 lesser than power of 2 i.e.

23  = 1000      and 23 – 1 = 111                 bitwise and of    (1000) &(111) = 0

24  = 10000      and 24 – 1 = 1111             bitwise and of     (10000) &(1111) = 0
…………….. So on.

So we have to find the number just lesser than the given input and do AND operation of both numbers. If output of and operation is 0 (zero) then we can say that number is power of 2.
Step 1:-

Take number in array input[] of ‘char’ type as number of bits may be more than range of (2^64).

Step 2:-

Use karnaugh map output for the binary number substraction shown below :-

From the above as fig. we can co-relate that :-
input[i] = A
borrow = B
negate(input[i]) = A’
negate(borrow) = B’

Borrow is calculated for the next operation in each iteration.Store the value of difference in array “justLess[]” i.e. it contains the number 1 less than original.

Note:- We are taking Borrow as B initially because it’s only Borrow which decides what will be the result in next step.

Step 3:-

Now perform bitwise AND operation on both the array (input[i] , justLess[i]) and terminate as soon as encountered with 1.
Otherwise number will be the power of 2. 🙂

Time Complexity:-  O(n)
Space Complexity:-
O(n)

C Implementaion:-

```#include <stdio.h>
int negate(int number)
{
if(number==1)
return 0;
else
return 1;
}
int main(void) {
char input[100000],justLess[100000];
int i,temp,borrow=1,result,final[100000],notPower=0;
printf("Enter the binary number of any length <= 100000\n");
scanf("%s",&input);
long int len = strlen(input);

for(i=len-1;i>=0;i--)
{
temp=(input[i]-48);
result = negate((input[i]-48))*borrow + negate(borrow)*(input[i]-48);
justLess[i]=result+48;
borrow = negate(temp) * borrow;

}
for(i=0;i<len;i++)
{
final[i] = (input[i]-48)&(justLess[i]-48);
if(final[i]==1)
{
notPower=1;
break;
}
}
if(notPower)
{
printf("Input is not a power of 2\n");
}
else
{
printf("Lets have some beer..!!...Input is a power of 2\n");
}

return 0;
}
```
Advertisements