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 :-
Capture

 

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

One thought on “The Power Of Two (more than 2^64)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s