<p>在<a href="https://stackoverflow.com/questions/39940954/python-fast-xor-over-range-algorithm">Python fast XOR over range algorithm</a>的可接受答案中,<em>存在一个缺陷:在进行异或计算之前,{a1}的递减需要在<em>之前完成。这是一个修复过的版本,以及一个<code>assert</code>测试来验证它是否给出了与朴素算法相同的结果。在</p>
<pre><code>def f(a):
return (a, 1, a + 1, 0)[a % 4]
def getXor(a, b):
return f(b) ^ f(a-1)
def gen_nums(start, length):
l = length
ans = 0
while l > 0:
l = l - 1
ans ^= getXor(start, start + l)
start += length
return ans
def answer(start, length):
c = val = 0
for i in xrange(length):
for j in xrange(length - i):
n = start + c + j
#print '%d,' % n,
val ^= n
#print
c += length
return val
for start in xrange(50):
for length in xrange(100):
a = answer(start, length)
b = gen_nums(start, length)
assert a == b, (start, length, a, b)
</code></pre>
<p>在<code>start</code>和<code>length</code>的范围内,<code>gen_nums</code>大约比<code>answer</code>快5倍,但我们可以通过消除这些函数调用使其速度再快一倍(即大约是<code>answer</code>的10倍):</p>
^{pr2}$
<hr/>
<p>正如Mirek Opoka在评论中提到的,<code>% 4</code>相当于{<cd9>},它更快,因为按位运算比执行整数除法和丢弃商更快。所以我们可以用</p>
<pre><code>ans ^= (b, 1, b + 1, 0)[b & 3] ^ (0, start - 1, 1, start, 0)[start & 3]
</code></pre>