記事概要

累積 xor 計算と、 計算に必要な xor 演算の特性についてです。

xor 計算の特性

• 任意の偶数 n について、 n xor (n + 1) = 1 が成立する
• (a xor b) xor c = a xor (b xor c) が成立する
• 0 xor 0 xor ... 1 xor 1 の値は 1 が奇数個のときは 1 であり、1 が偶数個のときは 0 である
• a xor a = 0
  • つまり (a xor b) xor b = a が成立する

累積 xor の計算

F(x) = 1 xor 2 xor ... x のとき
任意の偶数 n について、 n xor (n + 1) = 1 であることと
0 xor 0 xor ... 1 xor 1 の値は 1 が奇数個のときは 1 であり、1 が偶数個のときは 0 であることから
以下のような関数が成立する。

def F(x):
    if x % 2 == 1:
        if ((x - 1) // 2 + 1) % 2 == 1:
            return 1
        else:
            return 0
    return F(x - 1) ^ x

また、(a xor b) xor b = a であることから、
a xor (a + 1) xor (a + 2) xor ... b = F(B) xor F(A - 1)
が成立する。

類題

AtCoder ABC 121 D XOR World