Direct formula for summing XOR

Question

I have to XOR numbers from 1 to N, does there exist a direct formula for it ?

For example if N = 6 then 1^2^3^4^5^6 = 7 I want to do it without using any loop so I need an O(1) formula (if any)

Answer 1

Your formula is N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) ):

int main() {     int S = 0;     for (int N = 0; N < 50; ++N) {         S = (S^N);         int check = N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) );         std::cout << "N = " << N << ": "  << S << ", " << check << std::endl;         if (check != S) throw;     }      return 0; } 

Output:

N = 0: 0, 0             N = 1: 1, 1             N = 2: 3, 3 N = 3: 0, 0             N = 4: 4, 4             N = 5: 1, 1 N = 6: 7, 7             N = 7: 0, 0             N = 8: 8, 8 N = 9: 1, 1             N = 10: 11, 11          N = 11: 0, 0 N = 12: 12, 12          N = 13: 1, 1            N = 14: 15, 15 N = 15: 0, 0            N = 16: 16, 16          N = 17: 1, 1 N = 18: 19, 19          N = 19: 0, 0            N = 20: 20, 20 N = 21: 1, 1            N = 22: 23, 23          N = 23: 0, 0 N = 24: 24, 24          N = 25: 1, 1            N = 26: 27, 27 N = 27: 0, 0            N = 28: 28, 28          N = 29: 1, 1 N = 30: 31, 31          N = 31: 0, 0            N = 32: 32, 32 N = 33: 1, 1            N = 34: 35, 35          N = 35: 0, 0 N = 36: 36, 36          N = 37: 1, 1            N = 38: 39, 39 N = 39: 0, 0            N = 40: 40, 40          N = 41: 1, 1 N = 42: 43, 43          N = 43: 0, 0            N = 44: 44, 44 N = 45: 1, 1            N = 46: 47, 47          N = 47: 0, 0 N = 48: 48, 48          N = 49: 1, 1            N = 50: 51, 51 

Explanation:

1. Low bit is XOR between low bit and next bit.

2. For each bit except low bit the following holds:

   • if N is odd then that bit is 0.
   • if N is even then that bit is equal to corresponded bit of N.

Thus for the case of odd N the result is always 0 or 1.

Answer 2

edit
GSerg Has posted a formula without loops, but deleted it for some reason (undeleted now). The formula is perfectly valid (apart from a little mistake). Here's the C++-like version.

if n % 2 == 1 {
    result = (n % 4 == 1) ? 1 : 0;
} else {
    result = (n % 4 == 0) ? n : n + 1;
}

One can prove it by induction, checking all reminders of division by 4. Although, no idea how you can come up with it without generating output and seeing regularity.

Please explain your approach a bit more.
Since each bit is independent in xor operation, you can calculate them separately.
Also, if you look at k-th bit of number 0..n, it'll form a pattern. E.g., numbers from 0 to 7 in binary form.

000
001
010
011
100
101
110
111

You see that for k-th bit (k starts from 0), there're 2^k zeroes, 2^k ones, then 2^k zeroes again, etc.
Therefore, you can for each bit calculate how many ones there are without actually going through all numbers from 1 to n.

E.g., for k = 2, there're repeated blocks of 2^2 == 4 zeroes and ones. Then,

int ones = (n / 8) * 4; // full blocks
if (n % 8 >= 4) { // consider incomplete blocks in the end
    ones += n % 8 - 3;
}

Answer 3

For odd N, the result is either 1 or 0 (cyclic, 0 for N=3, 1 for N=5, 0 for N=7 etc.)

For even N, the result is either N or N+1 (cyclic, N+1 for N=2, N for N=4, N+1 for N=6, N for N=8 etc).

Pseudocode:

if (N mod 2) = 0
  if (N mod 4) = 0 then r = N else r = N+1
else
  if (N mod 4) = 1 then r = 1 else r = 0