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

Try this:

the LSB gets toggled each time the N is odd, so we can say that

 rez & 1 == (N & 1) ^ ((N >> 1) & 1)

The same pattern can be observed for the rest of the bits. Each time the bits B and B+1 (starting from LSB) in N will be different, bit B in the result should be set.

So, the final result will be (including N): rez = N ^ (N >> 1)

EDIT: sorry, it was wrong. the correct answer:

for odd N: rez = (N ^ (N >> 1)) & 1

for even N: rez = (N & ~1) | ((N ^ (N >> 1)) & 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

Lets say the function that XORs all the values from 1 to N be XOR(N), then

XOR(1) = 000 1 = 0 1 ( The 0 is the dec of bin 000)
XOR(2) = 001 1 = 1 1
XOR(3) = 000 0 = 0 0
XOR(4) = 010 0 = 2 0
XOR(5) = 000 1 = 0 1 
XOR(6) = 011 1 = 3 1
XOR(7) = 000 0 = 0 0
XOR(8) = 100 0 = 4 0
XOR(9) = 000 1 = 0 1
XOR(10)= 101 1 = 5 0
XOR(11)= 000 0 = 0 0
XOR(12)= 110 0 = 6 0

I hope you can see the pattern. It should be similar for other numbers too.

Answer 4

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

Answer 5

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 6

Great answer by Alexey Malistov! A variation of his formula: n & 1 ? (n & 2) >> 1 ^ 1 : n | (n & 2) >> 1 or equivalently n & 1 ? !(n & 2) : n | (n & 2) >> 1.