codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// Calculate xor of all numbers from 1 to N // Testing for numbers upto 150000 // Same concept works well for large numbers also #include <stdio.h> #include <stdlib.h> #include <limits.h> 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; }
Private
[
?
]
Run code
Submit