みんな早い...！！！

問題概要

2 つの整数 $A, B$ ( $A \le B$ ) が与えられる。 $A$ 以上 $B$ 以下のすべての整数の XOR 和を求めよ。

制約

$0 \le A \le B \le 10^{12}$

「A 以上 B 以下」と、「XOR の引き算」とは

まず「 $A$ 以上 $B$ 以下の値の総和を求めよ」という問題は、「 $X$ 以下の値の総和を求めよ」という問題だと思うことができる:

$B$ 以下の値についての答えから
$A-1$ 以下の値についての答えを引く

ここで「引く」という行為は、XOR 和においては XOR 和を取ること自体をさす。

一応そのことをちゃんと詰めてみる。引き算は足し算の逆として定義される。つまり $b - a$ とは $a + x = b$ を満たす $x$ のことである。

このことを XOR について考えてみる。すなわち

$a$ ^ $x = b$

を満たす $x$ とはなにかを考えてみる。両辺から $a$ ^ をとると $a$ ^ $a = 0$ より

$x = a$ ^ $b$

となる。つまり、XOR の世界では「足し算」も「引き算」も一緒なのだ。この考え方はすごく出て来る。

一応このことを知らなくても、

$Q = 0$ ^ $1$ ^ $2$ ^ $\dots$ ^ $(A-1)$ ^ $A$ ^ $(A+1)$ ^ $\dots$ ^ $B$
$P = 0$ ^ $1$ ^ $2$ ^ $\dots$ ^ $(A-1)$

とが求められていたら、

$Q$ ^ $P$ = $A$ ^ $(A+1)$ ^ $\dots$ ^ $B$

となってこれが答えになっているので、一般に「 $X$ 以下の整数の XOR 和」が求められればいいことは自然に導ける。

X 以下の整数の XOR 和

ひとまず桁ごとに考えるのが XOR の定石ではあると思う。つまり、 $d$ 桁目のみに着目したときに、 $0$ から $X$ までの整数を並べたときに $d$ 桁目に 1 が立っているものが奇数個か偶数個かを判定する問題ということになる。

今回は、結果的に実験してみるのが早い気がしていて 15 あたりまで書いてみると、

X	XOR 和
0	0
1	1
10	11
11	0
100	100
101	1
110	111
111	0
1000	1000
1001	1
1010	1011
1011	0
1100	1100
1101	1
1110	1111
1111	0

という感じになっている。気づくことは

$X$ が奇数のときは $0$ と $1$ を繰り返している (全体として $4$ 個ごとに足すと $0$ になっている)

ということ。その証明は後に回すとして、この性質を利用すると

$X$ が奇数のときは、 $\frac{X+1}{2}$ が偶数なら $0$ 、奇数なら $1$
$X$ が偶数のときは、 $X+1$ が奇数なのでその答えから $X+1$ を引く (XOR の意味で足す)

とすれば求められる。

#include <iostream>
using namespace std;

long long oddsolve(long long a) { return (a+1)/2 % 2; }
long long solve(long long a) {
    if (a % 2 == 1) return oddsolve(a);
    else return oddsolve(a+1) ^ (a+1);
}
int main() {
    long long A, B; cin >> A >> B;
    cout << (solve(B) ^ solve(A-1)) << endl;
}