Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У комп'ютерному програмуванні, XOR обмін (англ. XOR swap) — алгоритм, який використовує бітову операцію XOR для обміну значень різних змінних однакового типу даних без використання додаткової тимчасової змінної. Під словом «різні» мається на увазі, що значення змінних зберігається в різних адресах пам'яті; фактичні значення змінних не обов'язково повинні бути різними.
Алгоритм
Традиційний обмін значеннями потребує використання тимчасової змінної для збереження. При використанні алгоритму XOR обміну, не потрібно мати тимчасового збереження. Алгоритм виконується наступним чином:
X := X XOR Y Y := Y XOR X X := X XOR Y Алгоритм зазвичай відповідає трьом інструкціям машинного коду. Оскільки XOR є комутативною операцією, X XOR Y можна замінити на Y XOR X у будь-якому з цих рядків. При написанні коду на мові асемблер, ця комутативність часто використовується в другому рядку:
| Псевдокод | IBM (System/370) асемблер | x86 асемблер |
|---|---|---|
X := X XOR Y | XR R1,R2 | xor eax, ebx |
Y := Y XOR X | XR R2,R1 | xor ebx, eax |
X := X XOR Y | XR R1,R2 | xor eax, ebx |
У приведеному вище коді асемблеру для System/370, R1 і R2 є різними регістрами, і кожна операція XR записує свій результат у регістрі, що вказаний першим аргументом. При використанні асемблеру x86, значення X і Y знаходяться в регістрах eax і ebx (відповідно), а xor записує результат операції в перший регістр.
Однак, алгоритм не буде виконуватись, якщо x і y використовують одне сховище пам'яті, оскільки значення, що знаходиться за однією адресою будуть мати нульові значення після виконання першої інструкції XOR, і потім залишаться нулями; і це не буде заміною.
Доведення справедливості
Бітова операція XOR над послідовностями біт довжини 
має наступні властивості (де 
позначає XOR):
- L1. Комутативність:
![image]()
- L2. Асоціативність:
![image]()
- L3. Існування нейтральності: існує бітова послідовність, 0, (довжиною N), для якої виконується
![image]()
для будь-якого ![image]()
- L4. Кожен елемент є своїм власним оберненим: для кожного
![image]()
, ![image]()
.
Припустимо, що ми маємо два різні регістри R1 і R2 як показано нижче в таблиці, які мають початкові значення A і B відповідно. Виконаємо приведені нижче операції по черзі, і виконаємо спрощення за допомогою наведених вище властивостей.
| Крок | Операція | Регістр 1 | Регістр 2 | Перетворення |
|---|---|---|---|---|
| 0 | Початкове значення |  |  | — |
| 1 | R1 := R1 XOR R2 |  |  | — |
| 2 | R2 := R1 XOR R2 | |    | L2 L4 L3 |
| 3 | R1 := R1 XOR R2 |      |  | L1 L2 L4 L1 L3 |
Причини використання на практиці
Здебільшого, звичайний алгоритм обміну з використанням тимчасового регістра більш ефективний. Конкретні ситуації, в яких практично корисно застосувати XOR обмін є наступні:
- у процесорах де набір інструкцій дозволяє виконувати XOR обмін закодований за допомогою меншої кількості байт;
- у випадках з постійною нестачею вільних регістрів, це може дозволити уникнути застосування пам'яті замість регістрів;
- у мікроконтролерах де доступна пам'ять RAM дуже обмежена.
Оскільки ці ситуації не є частим, більшість оптимізувальних компіляторів ніколи не генерують коду з XOR обміном.
Приклад реалізації
За допомогою препроцесора мови C, цю функцію можна реалізувати наступним чином:
#define swapXOR(x,y) do { *x ^= *y; *y ^= *x; *x ^= *y; } while(0) int main (int argc, char** argv) { int x = 5; int y = 7; printf("%i, %i\n", x,y); // до заміни 5, 7 swapXOR(&x,&y); printf("%i, %i\n", x,y); // після 7, 5 } Див. також
Примітки
- . Cs.umd.edu. Архів оригіналу за 23 січня 2017. Процитовано 2 квітня 2014.
- . graphics.stanford.edu. Архів оригіналу за 8 січня 2020. Процитовано 2 травня 2014.
- Перші три властивості, разом із існуванням інверсії кожного з елементів, є визначенням абелевої групи. Остання властивість, є структурною особливістю XOR і не обов'язково поширюється на інші Абелеві групи.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U komp yuternomu programuvanni XOR obmin angl XOR swap algoritm yakij vikoristovuye bitovu operaciyu XOR dlya obminu znachen riznih zminnih odnakovogo tipu danih bez vikoristannya dodatkovoyi timchasovoyi zminnoyi Pid slovom rizni mayetsya na uvazi sho znachennya zminnih zberigayetsya v riznih adresah pam yati faktichni znachennya zminnih ne obov yazkovo povinni buti riznimi Vikoristannya algoritmu XOR obminu dlya zamini nibliv mizh dvoma zminnimi bez vikoristannya timchasovoyi zminnoyiAlgoritmTradicijnij obmin znachennyami potrebuye vikoristannya timchasovoyi zminnoyi dlya zberezhennya Pri vikoristanni algoritmu XOR obminu ne potribno mati timchasovogo zberezhennya Algoritm vikonuyetsya nastupnim chinom X X XOR Y Y Y XOR X X X XOR Y Algoritm zazvichaj vidpovidaye trom instrukciyam mashinnogo kodu Oskilki XOR ye komutativnoyu operaciyeyu X XOR Y mozhna zaminiti na Y XOR X u bud yakomu z cih ryadkiv Pri napisanni kodu na movi asembler cya komutativnist chasto vikoristovuyetsya v drugomu ryadku Psevdokod IBM System 370 asembler x86 asembler span class n X span span class w span span class o span span class w span span class n X span span class w span span class k XOR span span class w span span class n Y span span class nf XR span span class w span span class no R1 span span class p span span class no R2 span span class nf xor span span class w span span class no eax span span class p span span class w span span class no ebx span span class n Y span span class w span span class o span span class w span span class n Y span span class w span span class k XOR span span class w span span class n X span span class nf XR span span class w span span class no R2 span span class p span span class no R1 span span class nf xor span span class w span span class no ebx span span class p span span class w span span class no eax span span class n X span span class w span span class o span span class w span span class n X span span class w span span class k XOR span span class w span span class n Y span span class nf XR span span class w span span class no R1 span span class p span span class no R2 span span class nf xor span span class w span span class no eax span span class p span span class w span span class no ebx span U privedenomu vishe kodi asembleru dlya System 370 R1 i R2 ye riznimi registrami i kozhna operaciya XR zapisuye svij rezultat u registri sho vkazanij pershim argumentom Pri vikoristanni asembleru x86 znachennya X i Y znahodyatsya v registrah eax i ebx vidpovidno a span class nf xor span zapisuye rezultat operaciyi v pershij registr Odnak algoritm ne bude vikonuvatis yaksho x i y vikoristovuyut odne shovishe pam yati oskilki znachennya sho znahoditsya za odniyeyu adresoyu budut mati nulovi znachennya pislya vikonannya pershoyi instrukciyi XOR i potim zalishatsya nulyami i ce ne bude zaminoyu Dovedennya spravedlivostiBitova operaciya XOR nad poslidovnostyami bit dovzhini N displaystyle N maye nastupni vlastivosti de displaystyle oplus poznachaye XOR L1 Komutativnist A B B A displaystyle A oplus B B oplus A L2 Asociativnist A B C A B C displaystyle A oplus B oplus C A oplus B oplus C L3 Isnuvannya nejtralnosti isnuye bitova poslidovnist 0 dovzhinoyu N dlya yakoyi vikonuyetsya A 0 A displaystyle A oplus 0 A dlya bud yakogo A displaystyle A L4 Kozhen element ye svoyim vlasnim obernenim dlya kozhnogo A displaystyle A A A 0 displaystyle A oplus A 0 Pripustimo sho mi mayemo dva rizni registri R1 i R2 yak pokazano nizhche v tablici yaki mayut pochatkovi znachennya A i B vidpovidno Vikonayemo privedeni nizhche operaciyi po cherzi i vikonayemo sproshennya za dopomogoyu navedenih vishe vlastivostej Krok Operaciya Registr 1 Registr 2 Peretvorennya 0 Pochatkove znachennya A displaystyle A B displaystyle B 1 R1 R1 XOR R2 A B displaystyle A oplus B B displaystyle B 2 R2 R1 XOR R2 A B displaystyle A oplus B A B B A B B displaystyle A oplus B oplus B A oplus B oplus B A 0 displaystyle A oplus 0 A displaystyle A L2 L4 L3 3 R1 R1 XOR R2 A B A A A B displaystyle A oplus B oplus A A oplus A oplus B A A B displaystyle A oplus A oplus B 0 B displaystyle 0 oplus B B 0 displaystyle B oplus 0 B displaystyle B A displaystyle A L1 L2 L4 L1 L3Prichini vikoristannya na prakticiZdebilshogo zvichajnij algoritm obminu z vikoristannyam timchasovogo registra bilsh efektivnij Konkretni situaciyi v yakih praktichno korisno zastosuvati XOR obmin ye nastupni u procesorah de nabir instrukcij dozvolyaye vikonuvati XOR obmin zakodovanij za dopomogoyu menshoyi kilkosti bajt u vipadkah z postijnoyu nestacheyu vilnih registriv ce mozhe dozvoliti uniknuti zastosuvannya pam yati zamist registriv u mikrokontrolerah de dostupna pam yat RAM duzhe obmezhena Oskilki ci situaciyi ne ye chastim bilshist optimizuvalnih kompilyatoriv nikoli ne generuyut kodu z XOR obminom Priklad realizaciyiZa dopomogoyu preprocesora movi C cyu funkciyu mozhna realizuvati nastupnim chinom define swapXOR x y do x y y x x y while 0 int main int argc char argv int x 5 int y 7 printf i i n x y do zamini 5 7 swapXOR amp x amp y printf i i n x y pislya 7 5 Div takozhSimetrichna riznicya mnozhin Merezha FejstelyaPrimitki Cs umd edu Arhiv originalu za 23 sichnya 2017 Procitovano 2 kvitnya 2014 graphics stanford edu Arhiv originalu za 8 sichnya 2020 Procitovano 2 travnya 2014 Pershi tri vlastivosti razom iz isnuvannyam inversiyi kozhnogo z elementiv ye viznachennyam abelevoyi grupi Ostannya vlastivist ye strukturnoyu osoblivistyu XOR i ne obov yazkovo poshiryuyetsya na inshi Abelevi grupi