**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.

2^{3 }= 1000 and 2^{3} – 1 = 111 bitwise and of (1000) &(111) = 0

2^{4 }= 10000 and 2^{4} – 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; }

Reblogged this on DIgital Gurl.