xor

xorの性質

タグ xor bit

  • 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