关于异或

一个问题

给定两个非负整数数 'a,b (a≤b)'，求 a xor (a+1) xor (a+2) xor ... xor b

要求复杂度为 O(1)

分析

如果直接从 a 跑到 b，那肯定是 TLE 的

那么，我们就考虑一个结论：

对于任意整数 x，x xor x = 0 是显然的

那么，我们就可以这样化简：

a xor (a+1) xor (a+2) xor ... xor b = (1 xor 2 xor 3 xor ... xor b) xor (1 xor 2 xor 3 xor ... xor (a-1))

所以，只需要讨论 1 xor 2 xor ... k 的值就行了（k 为任意正整数）

注意，如果 a = 0，那么要特殊处理

否则，答案将会异或一个负数