החלפה בעזרת XOR

אלגוריתם ההחלפה של XOR משתמש בפעולת ה־XOR (פעולה לוגית שמחזירה 1 אם הביטים שונים ו‑0 אם שווים). האלגוריתם מחליף את הערכים של שני משתנים מאותו סוג בלי להשתמש במשתנה עזר. הרעיון מבוסס על הזהות A XOR A = 0 ועל זהות b XOR 0 = b.

בדרך הרגילה להחלפה נדרש משתנה עזר. באלגוריתם ה‑XOR מבצעים שלוש פעולות XOR בלבד:

X := X XOR Y
Y := X XOR Y
X := X XOR Y

ברמת המכונה זה בדרך כלל דורש שלוש פקודות. לדוגמה, באסמבלר זה יכול להיראות כך: XOR R1, R2; XOR R2, R1; XOR R1, R2. בשפות מסוימות קיימת פקודה ייעודית שנקראת XCHG שמחליפה ערכים ביעילות רבה יותר.

דוגמה מספרית: נניח X = 12 ו‑Y = 10. בבינארי זה 1100 ו‑1010. אחרי הפעולה הראשונה X מקבל את X XOR Y. אחרי הפעולה השנייה Y מקבל את הערך המקורי של X. אחרי הפעולה השלישית X מקבל את הערך המקורי של Y. בסוף הערכים הוחלפו.

מבחינה מתמטית זה נכון לכל X ו‑Y כי XOR היא אסוציאטיבית וקומוטטיבית, ובגלל הזהויות a XOR a = 0 ו‑b XOR 0 = b.

XOR AX, BX
XOR BX, AX
XOR AX, BX

xor $a0, $a0, $a1
xor $a1, $a0, $a1
xor $a0, $a0, $a1

Var1 = Var1 Xor Var2
Var2 = Var2 Xor Var1
Var1 = Var1 Xor Var2

x ^= y;
y ^= x;
x ^= y;

פונקציות שמממשות זאת לא יעבדו אם שני הפרמטרים מצביעים לאותו מקום בזיכרון. במצב כזה הערך עלול להפוך ל‑0.

טכניקה זו שימושית בתכנות ברמת מכונה, כששטח אחסון או אוגרים הם מצרך יקר. היא מפחיתה גישות לזיכרון ועשויה לחסוך משאבים. עם זאת, במעבדים מודרניים טכניקת ה‑XOR עלולה להיות איטית יותר משימוש במשתנה זמני. זאת משום שהפקודות תלויות בתוצאות הקודמות, ולכן קשה לבצע אותן במקביל. אם מהירות קריטית, מומלץ להשוות בין שתי השיטות על אותה מערכת.

אלגוריתם ההחלפה של XOR מחליף שני ערכים בלי משתנה נוסף. XOR היא פעולה על ביטים. אם הביטים שונים היא נותנת 1. אם הביטים שווים היא נותנת 0.

שלוש הפעולות הקטנות שעושות את כל העבודה הן:

X := X XOR Y
Y := X XOR Y
X := X XOR Y

דוגמה קצרה: X = 12 (1100) ו‑Y = 10 (1010). אחרי שלושת השלבים הערכים מחליפים מקומות.

XOR AX, BX
XOR BX, AX
XOR AX, BX

xor $a0, $a0, $a1
xor $a1, $a0, $a1
xor $a0, $a0, $a1

Var1 = Var1 Xor Var2
Var2 = Var2 Xor Var1
Var1 = Var1 Xor Var2

x ^= y;
y ^= x;
x ^= y;

שימו לב: השיטה לא עובדת אם שני הפרמטרים הם אותו מקום בזיכרון. במחשבים מודרניים לפעמים עדיף להשתמש במשתנה זמני כי זה מהיר יותר שם.