Алгоритм обмена XOR в Python?

Question

Я пытался реализовать XOR swap в python.

x,y= 10,20

x,y,x = x^y,x^y,x^y

print('%s , %s'%(x,y))

ВЫВОД:

30 , 30

Я не новичок в python, но я не могу объяснить этот вывод. Это должно было быть 20,10.

Что происходит под капотом?

Answer 1

Сначала создается кортеж, состоящий из x^y, x^y и x^y. Затем кортеж распаковывается в x, y и x, в результате чего оба будут связаны с результатом x^y.

Избавь себя от головной боли и сделай это по-Питонски:

x, y = y, x

Answer 2

Хотя определенно лучше, как говорят другие ответы, просто x, y = y, x, если у вас аллергия на создание и распаковку кортежей, вы можете сделать это с помощью последовательного x-oring ... просто быть последовательным, а не одновременным , как вы делаете!

>>> x = 1234
>>> y = 3421
>>> x ^= y
>>> y ^= x
>>> x ^= y
>>> print x
3421
>>> print y
1234

Ключ к уловке подстановки xor состоит из трех последовательных xors, то есть одного после другого - трех отдельных операторов ^= в этом фрагменте. Конечно, это не имеет никакого практического смысла, но, если вы действительно заинтересованы в этом, он работает в Python, как и везде; -).

Answer 3

Вам необходимо записать строку «алгоритм» для строки.

>>> x, y = 10, 20
>>> x = x ^ y; print x, y
30 20
>>> y = x ^ y; print x, y
30 10
>>> x = x ^ y; print x, y
20 10
>>>

Вам нужно прочитать оставшуюся часть статьи в Википедии, в которой объясняется, что правильная реализация блокирует параллельные операции, и что вся идея в значительной степени бесполезна (по крайней мере, для современных компьютерных архитектур).

Answer 4

Алгоритм обмена XOR имеет смысл, только если у вас есть два указателя на изменяемые объекты. a и b являются двумя ссылками на неизменяемые целые числа.

РЕДАКТИРОВАТЬ (переход от комментариев к запросу и расширение):

Целые числа Python неизменны. Таким образом, каждый раз, когда вы «модифицируете» один с помощью XOR, будет выделяться новое хранилище (или повторно использоваться, например, для интернирования). Это принципиально отличается от (например, C), где swap изменяет значение без выделения новой памяти. Иными словами, подкачка XOR не создает новые объекты в смысле C99 («область хранения данных в среде выполнения, содержимое которой может представлять значения») или в смысле Python. Как отмечено здесь , настоящий XOR-своп может «обмениваться значениями переменных a и b без использования дополнительного пространства для временной переменной».

Или опытным путем:

>>> x = 3
>>> y = 5
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  3 , id(x):  137452872 y:  5 , id(y):  137452848
>>> x ^= y
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  6 , id(x):  137452836 y:  5 , id(y):  137452848
>>> y ^= x
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  6 , id(x):  137452836 y:  3 , id(y):  137452872
>>> x ^= y
>>> print "x: ", x, ", id(x): ", id(x), "y: ", y, ", id(y): ", id(y)
x:  5 , id(x):  137452848 y:  3 , id(y):  137452872

В этом случае мы видим, что интерпретатор (2.6.4) выглядит как , заключающий целые числа , поэтому x заканчивается адресом памяти, который изначально имел y Но главное в том, что для свопинга требуется как минимум одно выделение (137452836), а x и y не сохраняют один и тот же адрес памяти.

В С:

int x = 3;
int y = 5;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
x ^= y;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
y ^= x;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);
x ^= y;
printf("x: %d, &x: %p, y: %d, &y: %p\n", x, &x, y, &y);

дает:

x: 3, &x: 0xbfd433ec, y: 5, &y: 0xbfd433e8
x: 6, &x: 0xbfd433ec, y: 5, &y: 0xbfd433e8
x: 6, &x: 0xbfd433ec, y: 3, &y: 0xbfd433e8
x: 5, &x: 0xbfd433ec, y: 3, &y: 0xbfd433e8

Это настоящий XOR-своп, поэтому x и y всегда сохраняют одни и те же области памяти, а временные нет.

Answer 5

Вы можете легко сделать этот обмен, используя следующее:

x, y = 10, 20
x, y = y, x
print((x,y))

Что касается поведения, которое вы наблюдаете, я почти уверен, что это потому, что вся RHS оценивается, а затем присваивается LHS одновременно, и x^y всегда равно 30 в этом случае.