XOR и слишком много итераций?

Question

Мне была предложена следующая задача: учитывая s и x, вычислить количество решений (a, b), которые удовлетворяют как 1) s = a + b, так и 2) x = a XOR b. Все величины и операции являются целыми.

Example Inputs: 
    s = 10 
    x = 4 
Output: 
    2 

Никакие модули не могут быть импортированы.

Я написал следующие ответы, которые все слишком долго:

Первое:

def answer(s,x): 
    tally = 0 
    z = 0 
    while z <= s: 
     p = s - z 
     q = int(z^p) 
     if x == q: 
      tally += 1 
     z += 1 
    return tally 

Второе:

def answer(s,x): 
    spotlist, forwardlist = range(0,s+1) 
    backwardlist = range(s,-1,-1) 
    tally = 0 
    for spot in spotlist: 
     if x == forwardlist[spot]^backwardlist[spot]: 
      if s == forwardlist[spot] + backwardlist[spot]: 
       tally +=1 
    print tally 

Третье:

def answer(s,x): 
    tally = 0 
    z = 0 
    while z <= s: 
     q = int(z^(s - z)) 
     if x == q: 
      tally += 1 
     else: 
      pass 
     z += 1 
    print tally 

Я думаю, что я» m что-то не хватает или итерации по номерам перед удалением некоторых возможных решений.

Answer 1

Если (a, b) - пара решений, то это также (b, a), поэтому вы можете уменьшить диапазон, который вы проверяете наполовину. Кроме того, вы можете воспользоваться тем, что если x = a^b то b = x^a

Код ниже более чем в два раза быстрее, чем ваш первый answer() функции
с s, x = 10, 4, и более чем в 4 раза быстрее с s, x = 255, 255.

def xorsum(s, x): 
    tally = 0 
    for a in xrange(s//2 + 1): 
     tally += s - a == x^a 
    return 2 * tally 

Эта функция использует тот факт, что в Python False и True имеют числовые значения 0 и 1, соответственно. Выполнение этого происходит быстрее, чем использование теста if и только приращение tally, если тест верен.

Вы могли реализовать xorsum, используя список понимание:

def xorsum_lc(s, x): 
    return 2 * sum([s - a == x^a for a in xrange(s//2 + 1)]) 

но это медленнее, чем выше функции; эквивалентное выражение генератора еще медленнее (как и ожидалось).