Shivkumar Shivkumar - 1 year ago 120
Python Question

Xor logic in python

I have solved this problem from 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 Source

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)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download