c++ - 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.