Короткие заметки о математике и программировании

Короткие заметки о математике и программировании

xor_inv

Доказательство обмена через XOR

Конспект
✍️XOR переключает биты: a ^ b ^ b = a
✍️Пошаговое доказательство для a0, b0
✍️Обмен без временной переменной всегда работает корректно

Лекция
В прошлой заметке мы показали XOR‑обмен на примере и таблице. Демонстрация — это не доказательство. Ниже — краткое строгое объяснение, почему XOR‑обмен работает.

Думайте о a ^ b как о переключении (инвертировании) битов a в тех позициях, где у b стоят 1. Дважды инвертируем — получаем исходное: a ^ b ^ b = a.

// Пусть исходные значения — a0 и b0
let a = a0, b = b0
a = a ^ b      // a = a0 ^ b0,        b = b0
b = a ^ b      // a = a0 ^ b0,        b = b0 ^ (a0 ^ b0) = a0
a = a ^ b      // a = a0 ^ b0 ^ a0 = b0, b = a0

Результат общий: значения меняются местами без временной переменной для любых целых a0 и b0.

#education #devTopic #junior