Xor Range without LOOP

This post is shamelessly lifted from http://topforces.blogspot.com/2011/06/xor-range-without-loop.html

I am lazy, and I wont be able to explain it more clearly than him. Hence, I lifted the content directly from there, to have all the coding tricks in my blog for my reference. 

----------------------

HOW to get Xor between numbers from 1 to 300000000

you will get TLE if you try to use Loop for all numbers
Question was asked on the codeforces site. Click Here to see the discussion 

jacob answer
Let's introduce
 f(x) = x ^ (x-1) ^ (x-2) ^ ... ^ 1
Then anwer would be  
f(end) ^ f(start - 1)


Let's now learn to calculate f(x) fast enough. First, notice that f(4*k - 1) = 0 (provable by induction). So to calculate f(x) you only need to take at most 4 last numbers and xor them.
Finally,
f(4*k) = 4*k
f(4*k + 1) = 1
f(4*k + 2) = 4*k + 3
f(4*k + 3) = 0 


Expressions "at most 4 last numbers" and "only last 4 numbers" are different. In fact, you need to take exactly (x+1)%4 last numbers.

Conclusion:Use this function 

int f(int n){  
switch(n%4){  
case 0: return n;  
case 1: return 1;  
case 2: return n+1;  
default: return 0;  
}  
}