// 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;
}

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