python 中的异或逻辑

Question

我已经使用 python(v2)

从 hackerearth.com 解决了这个问题

问题陈述：Xor is Mad

我的代码是：

tests = int(raw_input())
for i in range(tests):
x = int(raw_input())
c = 0
b = x
a = x-1
while a > 0:
    xor = a^b
    summ =  b + a
    # print "XOr : ",xor
    # print "Sum : ",summ,"\n--------"
    if xor == summ:
        c += 1
        a -= 1
    elif a > 0:
        a -= 1 
print c

但我遇到了输入超时问题：输入#5 到#9

有人可以用不同的方式解决这个问题来管理要在 1 秒内执行的测试吗？

Answer 1

诀窍是认识到您不必测试所有 a 直至 x。对于 a^x == a+x，然后是 a&x == 0。所以我们计算 x 的位串中零的数量然后得到答案是 2**count -1

test = int(input())
for _ in range(test):
    x = int(input())
    print(2**bin(x)[2:].count('0') -1)

python 中的异或逻辑

Xor logic in python

python

performance

bitwise-xor