XOR 和 sum 迭代太慢？

Question

我遇到了以下问题：给定 s 和 x，计算同时满足 1) s = a + b 和 2) x = a XOR b 的解 (a,b) 的数量。所有数量和操作都是整数。

Example Inputs:
    s = 10
    x = 4
Output:
    2

无法导入任何模块。

我写了以下答案，但都花了太长时间：

第一个：

def answer(s,x):
    tally = 0
    z = 0
    while z <= s:
        p = s - z
        q = int(z ^ p)
        if x == q:
            tally += 1
        z += 1
    return tally

第二个：

def answer(s,x):
    spotlist, forwardlist = range(0,s+1)
    backwardlist = range(s,-1,-1)
    tally = 0
    for spot in spotlist:
        if x == forwardlist[spot] ^ backwardlist[spot]:
            if s == forwardlist[spot] + backwardlist[spot]:
                tally +=1
    print tally

第三名：

def answer(s,x):
    tally = 0
    z = 0
    while z <= s:
        q = int(z ^ (s - z))
        if x == q:
            tally += 1
        else:
            pass
        z += 1
    print tally

我想我在删除某些可能的解决方案之前遗漏了一些东西或迭代了数字。

Answer 1

如果(a,b)是一个解决方案对，那么(b,a)也是一个解决方案对，因此您可以将测试范围缩小一半。此外，您可以利用 if x = a ^ b then b = x ^ a

这一事实

下面的代码比您的第一个 answer() 函数快两倍多
s, x = 10, 4，速度提高了 4 倍以上 s, x = 255, 255.

def xorsum(s, x):
    tally = 0
    for a in xrange(s//2 + 1):
        tally += s - a == x ^ a 
    return 2 * tally

这个函数利用了Python的False和True的数值分别为0和1的事实。这样做比使用 if 测试更快，并且只有在测试为真时才递增 tally。

您可以使用列表推导实现xorsum：

def xorsum_lc(s, x):
    return 2 * sum([s - a == x ^ a for a in xrange(s//2 + 1)])

但比上面的功能慢；等效的生成器表达式甚至更慢（正如预期的那样）。

XOR 和 sum 迭代太慢？

XOR and sum iterations too slow?

python

performance

bit-manipulation