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

Question

Я решил эту проблему с помощью hackerearth.com питона (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)