xorの性質
- grundy数などのユニークな性質を計算することができる
区間 [a, b] の整数のxorの累積
f(a, b) = a ^ a1 ^ ... ^ b(n-1) ^ bのこと
f(0, a-1) = 0 ^ 1 ^ ... ^ a-1とf(0, b) = 0 ^ 1 ^ ... ^ bがあったとき、f(a, b) = f(0, b) ^ f(0, a-1)
このとき、n ^ (n+1)は1になる性質があるから、それぞれペアを作り以下の一般化が成立する
愚直
# xorの累積
N = 8
a = 0
for i in range(N+1):
a ^= i
print(a) # 8
一般化
def calc(x):
if x%2 == 0:
return calc(x+1) ^ (x+1)
else:
if ((x+1)//2)%2 == 0:
return 0
else:
return 1
print(calc(8)) # 8