```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ``` ```// Calculate xor of all numbers from 1 to N // Testing for numbers upto 150000 // Same concept works well for large numbers also #include #include #include unsigned int xor_n(unsigned int upto) { unsigned int ans = upto; while(--upto) ans ^= upto; return ans; } unsigned int xor_logn(unsigned int upto) { int nbits = sizeof(unsigned int) * CHAR_BIT; unsigned int ans = ( (upto+1) / 2) & 1; int i; for(i = 1; i < nbits-1; ++i) { int parity = upto % (2 << i); if(parity < (1 << i) ) continue; parity -= (1 << i) - 1; if(parity & 1) ans |= (1 << i); } /* if( upto > 1 << (nbits - 1) ) ans |= (upto&1) ? 1 << nbits : 0; */ return ans; } unsigned int xor_const(unsigned int upto) { unsigned int ans[] = {upto, 1, upto+1, 0}; return ans[upto%4]; } int main() { int i; for(i = 0; i < 10; ++i) { unsigned int upto = rand() % 150000; unsigned int expected = xor_n(upto); unsigned int method1 = xor_logn(upto); unsigned int method2 = xor_const(upto); if(method1 == expected && method2 == expected) { printf("ok for %u\n", upto); } else { printf("Arg = %u, expected = %u, method1 = %u, method2 = %u\n" , upto, expected, method1, method2); } } return 0; } ```
 ```1 2 3 4 5 6 7 8 9 10 ``` ```ok for 89383 ok for 30886 ok for 42777 ok for 136915 ok for 97793 ok for 38335 ok for 35386 ok for 60492 ok for 116649 ok for 141421 ```