Shivkumar Shivkumar - 22 days ago 8
Python Question

Xor logic in python

I have solved this problem from hackerearth.com using python(v2)

Problem statement: Xor is Mad

My code is :

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


but I have time exceeding problem for inputs : input#5 to #9

can somebody solve this problem in different way to manage the tests to be executed in 1sec.

Answer

The trick is to recognize that you don't have to test all the a up to x. For a^x == a+x, then a&x == 0. So we count the number of zeroes in the bitstring of x and then out answer is 2**count -1

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