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
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)
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