given M and N, calc M xor M+1 xor ... xor N

xor.cpp

// vim: shiftwidth=2 expandtab foldmethod=marker

// include {{{
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <utility>
#include <cstdlib>
// }}}

// debug(...) {{{
#ifdef LOCAL_DEBUG
#include "./debug.h"
#else
#define debug(...)
#define debugn(...)
#define debug_reset()
#endif

#include <cstdio>

template<class T>
std::string bin(int bits, const T& x) {
  char buf[bits + 1];
  buf[bits] = '\0';
  for(int i = 0; i < bits; i++) {
    if((x >> i) & 1) {
      buf[bits - i - 1] = '1';
    } else {
      buf[bits - i - 1] = '0';
    }
  }
  return std::string(buf);
}
std::string bin(int x) {
  if(x < 0) return bin(32, x);
  for(int i = 4; i < 31; i++) {
    int y = 1 << i;
    if(x < y) return bin(i, x);
  }
  return bin(32, x);
}
// }}}

// misc {{{
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

template<class T>
void sort(T& arr) {
  std::sort(arr.begin(), arr.end());
}
template<class T, class By>
void sort_by(T& arr, By by) {
  std::sort(arr.begin(), arr.end(), [by](auto l, auto r){return  by(l) < by(r); });
}

template<class T>
void reverse(T& arr) {
  std::reverse(arr.begin(), arr.end());
}

// }}}

// main {{{
void solve();
int main() {
  solve();
}
// }}}

int naive(int M, int N) {
  int ans = 0;
  rep2(i, M, N + 1) {
    ans ^= i;
  }
  return ans;
}

int o1(int M, int N) {
  int h = N - M + 1;
  int mask = 1;
  int ans = 0;
  rep(i, 31) {
    int l = 1 << i;
    int l2 = l * 2;
    int off = M & mask;

    if(l2 - off > h) {
      int n1 = max(off + h - l, 0);
      if(n1 % 2 == 1) ans |= (1 << i);
      debugn(i, l, off, n1);
    } else {
      int n1 = min(l, l2 - off);
      int n2 = l * ((h - l2 + off) / l2);
      int n3 = max(0, (h - l2 + off) % l2 - l);
      if((n1 + n2 + n3) % 2 == 1) ans |= (1 << i);
      debugn(i, l, off, n1, n2, n3);
    }
    mask = (mask << 1) | 1;
  }
  return ans;
}
void solve() {
  int M, N;
  cin >> M >> N;
  int ans1 =  naive(M, N);
  int ans2 = o1(M, N);
  rep2(i, M, N + 1) {
    debugn(bin(i), i);
  }
  debug_reset();
  debugn(N, M, bin(N), bin(M));
  debugn(ans1, ans2, bin(ans1), bin(ans2));

  cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << endl;
}