Efficient method to calculate XOR series

-
A XOR series between integer a and b (a<=b) can be defined as the xoring result of all elements between a and b (inclusive of a and b);

1. For Series from 1 to n:

f(n)=1^2^3^4^5...^n

But for XOR it holds a noticeable outcome
n Binary XOR from 1->n
1 0001 0001
2 0010 0011
3 0011 0000
4 0100 0100
5 0101 0001
6 0110 0111
7 0111 0000
8 1000 1000

From this result we can conclude that :
1. An element just before multiple of 4 results 0;
2. An element divisible by 4 results as the same.
3. An element just after the multiple of 4 results 1;
4. An element after 2 element from multiple of 4 results as the element is self +1

We can formulate the above as:

r=n%4:
 case r==0: XOR=n
 case r==1: XOR=1
 case r==2: XOR=n+1
 case r==3: XOR=0

2. For Series from a to b :

 In this case we do,
f(a) ^ f(b) = (1^2^3^4...^a) ^ (1^2^3^4...^b)=XOR(a,b)

Comments

Post a Comment

Popular posts from this blog

Efficient Method to Calculate Power

-
For a^b=(a X a X a X a.....X a) eg. for a=3, b=10 This can be written as 3^10 = (3^5)^2 Using this logic we can implement long long power(long long a, long long b){     long long res=1;     while(b>0){          if(b%2==1)//Odd Number{              res*=a;          }          a*=a;          b/=2;     }     return res; }
Read more

Efficient way to print factors of a number

-
Factors of a number n can be defined as the set of numbers which are divisible by n. eg. n=24 factors={1,2,3,4,6,8,12,24}; On native approach this can be done in time complexity O(n), but on efficient approach this can be done in O(sqrt(n)); For n=100; its factors are 1,2,4,5,10,20,25,50,100; If noticed carefully, it exists in pair, whose product form the number n; (1,100),(2,50),(4,25),(5,20),(10,10), we can see an exception for middle element 10, for odd numbers of factors. Similarly for n=24; factors: 1,2,3,4,6,8,12, 24 pairs: (1,24),(2,12),(3,8),(4,6) Further we can notice few more points: 1.  If (a,b) is a pair, 1<=a<=sqrt(n) 2. If (a,b) is a pair, b=n/a; as a*b=n Therefore progmatically, void Facotrs(int n){     for(int i=1;i<=sqrt(n);i++){         if(n/i=i)//OR i*i==n , for equal divisor element        {            print(i);         }   ...
Read more