Algo to find power of 2 does not work

general
, ,
1

#include
#include
using namespace std;

int main() {

	unsigned long long int n;
	cin>>n;
	double a=log(n)/log(2);
	double b=floor(a);

	if(a-b!=0)  
	    cout<<"NIE"<<endl;
	else
        cout<<"TAK"<<endl;
}

Getting Wrong Answer for the above code.
Constraints:
n<=10^14

2

Try this code.

Logic is: a number which is power of 2 form has only one “1” in its binary representation.
For example:

2 = 10

4 = 100

8 = 1000

16 = 10000

and numbers which are not of 2 power form contain more than one “1” in their binary representation

For example:

3 = 11

5 = 101

7 = 111

10 = 1010

And your code does not work because there are precision issues in using double like when dividing when may lose some bits. And also never try to compare two double values. Why? Discussed here.

Another way: mentioned by @rjohari and @lebron

If bitwise AND (&) of number “N” and “N-1” is zero then , “N” is of power 2 form otherwise not.

if((n&(n-1))==0)
    cout<<n<<" is power 2 form"<<endl;
else 
   cout<<n<<" is not power 2 form<<endl;

For example:

n = 8 , in bit representation 8=1000

n-1 = 7 , in bit representation 7=0111

1000 & 0111 = 0000

n = 4 , in bit representation 4=100

n-1 = 3 , in bit representation 3=011

100 & 011 = 000

n = 7 , in bit representation 7=111

n-1 = 6 , in bit representation 6=110

111 & 110 = 110

1 Like
3

your code will produce error integer constant is too large for ‘long’ type on large inputs.

Alternate solution: Use bitwise and to check if number is power of 2 or not. If a number N is power of 2 then bitwise and of N and N-1 is zero.

4

Hint:

if ((n&(n-1))==0)…