RangeOperation on A(m, n) = m & (m+1) & ... & (n-1) & n,

 RangeOperation

Let us define A(m, n) = m & (m+1) & ... & (n-1) & n, where & is the bitwise AND operation.
Write a program that, given 64-bit unsigned longs m and n, computes A(m, n).


Example Inputs:
49 54
2 2
2 3


Outputs (respectively):
48
2
2


Explanation:
A(49, 54)=49&50 &51&52&53&54= 48
A(2, 2) =2.If m= n,A(m, n)=m =n.
A(2, 3) =2& 3 =2

Let k be the bit width (maximum number of bits) of the primitive.
Easy: O(n -m) time. Consider that since m and n can be any 64-bit numbers, this could be
huge.
Moderate-Hard: O(k) time.
Hard: O(log(k)) time.

1.Complexity O(k)

#include <iostream>
 
using namespace std;
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int temp,k=~0,d;
d=m-n;
while(d)
{
k<<=1;
n=n&m&k;
d>>=1;
 
}
return n;
}
int main()
{  unsigned long int n,m;
     cin>>n>>m;
   cout <<RangeOperation(n,m)<< endl; 
   
   return 0;
}

other way of doing of the above complexity

//RangeOpearation with K complexity
#include <iostream>
 
using namespace std;
 
int MaxBit(unsigned long int n)
{
unsigned long int k=1;int p,count=0,i=0;
while(i<32)
{
    
if(k&n)
p=count;
count++;
k<<=1;
i++;
}
return p;
}
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int p,q,k,t=0;    
p=MaxBit(n);
q=MaxBit(m);
if(p!=q)
return 0;
k=MaxBit(m-n);
 
k=~t<<k;
return m&n&k;
}
 
int main()
{
     
    unsigned long int n,m;
     cin>>n>>m;
     cout <<"value is: "<< RangeOperation(n,m) << endl; 
     return 0;
}


2. With complexity O(logK)


//RangeOperation complexity logk.
 
#include <iostream>
 
using namespace std;
 
int MaxBit(unsigned long int n)
{
unsigned long int p=1,k=0;int left=0,right=31,mid;
 
 
while(n)
{
k=0,p=1;    
mid=(left+right)/2;
k=~(~k<<mid+1);
p=p<<mid;
if(n<=k && n&p)
{
return mid+1;    
}
else if(n>k)
{
left=mid;    
}
else
 right=mid;
 
}
return 0;
}
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int p,q,k,t=0;    
p=MaxBit(n);
q=MaxBit(m);
if(p!=q)
return 0;
k=MaxBit(m-n);
 
k=~t<<k;
return m&n&k;
}
 
int main()
{
     
    unsigned long int n,m;
     cin>>n>>m;
     cout <<"value is: "<< RangeOperation(n,m) << endl; 
     return 0;
}