# XOR of integers from 1 to n

A funny (but probably useless) formula. The left-hand side is the XOR of
integers from 1 to *n*, the operators are the usual C bitwise operators.

1 ^ ... ^ *n* = (*n* >> 1) & 1 ^ (*n*&1 ? 1 : *n*)

It's totally trivial to prove (just write the sequence of XOR values and look at the pattern), but, before you think about it, it's not that obvious that a closed formula exists.

Of course, this formula directly yields a closed-form expression of the XOR
of integers from *m* to *n*, for any *m* and *n*:
just compute the XOR of integers from 1 to *m*-1 and from 1 to *n*
and XOR them together. Thanks to Nathan D. Ryan for suggesting this.