Xor логика в питоне

Question

Я решил эту проблему с hackerearth.com с помощью Python(v2)

Постановка проблемы: 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)