החלפה בעזרת XOR

תרשים של ביצוע פעולת החלפה בעזרת XOR

אלגוריתם ההחלפה של XOR הוא אלגוריתם המשתמש בפעולה הלוגית XOR להחלפת ערכי שני משתנים, בעלי אותו סוג מידע, שאין ביניהם חלקים חופפים, ללא שימוש במשתנה עזר זמני. האלגוריתם משתמש בתכונת ההפרש הסימטרי של פעולת ה-XOR שהיא - A XOR A שווה תמיד ל-0 ("שקר"), לכל A.

האלגוריתם

אלגוריתמים סטנדרטיים להחלפת ערכים של שני משתנים דורשים שימוש במשתנה עזר. למשל, להלן אלגוריתם בסיסי להחלפת שני משתנים - X ו-Y:

• העתק את ערך Y למשתנה העזר
• העתק את ערך X למשתנה Y
• העתק את ערך משתנה העזר למשתנה X

לעומת זאת, אלגוריתם ה-XOR מבטל את הצורך במשתנה עזר. להלן תיאורו:

• הפעל XOR על X ו-Y והעתק את התוצאה ל-X
• הפעל XOR על X ו-Y והעתק את התוצאה ל-Y
• הפעל XOR על X ו-Y והעתק את התוצאה ל-X

האלגוריתם נראה פשוט יותר כשהוא כתוב בפסאודו-קוד:

X := X XOR Y

Y := X XOR Y

X := X XOR Y

דבר זה מוביל לכך שיש צורך ב-3 פקודות בשפת מכונה לביצוע האלגוריתם. לדוגמה, באסמבלר של מחשב ה-IBM 370 זה ייראה כך:

אנימציית החלפה של 2 אוגרים (רגיסטרים) אחד בשני בעזרת אלוגריתם XOR. הכחול מייצג את האוגר הראשון, והאדום מייצג את האוגר השני. הערך של שניהם בסוף מתחלף.

XOR R1, R2

XOR R2, R1

XOR R1, R2

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

הסבר

לדוגמה, נניח שיש לנו שני ערכים - X = 12 ו-Y = 10. בבינארית זה ייראה כך:

X = 1 1 0 0

Y = 1 0 1 0

כשנפעיל XOR על שני המשתנים אנו נקבל 0 1 1 0, אותו נעתיק למשתנה X. עתה יש לנו:

X = 0 1 1 0

Y = 1 0 1 0

כשנפעיל XOR שוב, נקבל 0 0 1 1. נעתיקו למשתנה Y. עתה יש לנו:

X = 0 1 1 0

Y = 1 1 0 0

לבסוף, נפעיל XOR ונקבל 0 1 0 1 - אותו שוב נשים ב-X. קיבלנו:

X = 1 0 1 0

Y = 1 1 0 0

כלומר, המשתנים החליפו את הערכים ביניהם, והאלגוריתם עבד במקרה זה.

באופן כללי, נסמן X=x ,Y=y (כלומר ערכים כלשהם), ונבצע את השלבים של האלגוריתם, כאשר נסמן את ה-XOR בסימן ⊕ (סימונו המקובל), ונזכור את הזהויות a ⊕ a = 0 ו-b ⊕ 0 = b (זהויות לוגיות שקל להוכיח) ואת העובדה ש-XOR היא פעולה אסוציאטיבית וקומוטטיבית. אזי -

• X = x ⊕ y, Y = y
• X = x ⊕ y, Y = x ⊕ y ⊕ y = x
• X = x ⊕ y ⊕ x = y, Y = x

כלומר, ראינו שגם כללית, האלגוריתם נכון.

דוגמאות קוד

שפת מכונה של x86

הקוד הבא הוא בשפת מכונה של x86, אשר משתמש באלגוריתם ההחלפה של XOR כדי להחליף את הערכים של האוגרים AX ו־BX, ללא שימוש באוגר זמני:

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

למעשה, כל המעבדים השייכים לארכיטקטורה זו כוללים את הפקודה XCHG אשר מבצעת את אותה הפעולה על האופרנדים שלה בצורה יותר אפקטיבית מאשר רצף פעולות ה־XOR הנ״ל.

MIPS architecture

דוגמה לקוד בארכיטקטורת MIPS אשר מחליפה את הערכים באוגרים a0,a1 בעזרת אלגוריתם הXOR:

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

Visual Basic

התת-רוטינה הזו של Visual Basic מחליפה את הערכים של הפרמטרים שלה בעזרת אלגוריתם הXOR:

 Sub Swap (Var1, Var2)
 Var1 = Var1 Xor Var2
 Var2 = Var2 Xor Var1
 Var1 = Var1 Xor Var2
 End Sub

שפת תכנות C

קוד של שפת התכנות C אשר מבצעת את האלגוריתם על המשתנים X ו־Y:

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

ניתן ליישם את האלגוריתם גם כמאקרו לקדם־מעבד (preproccessor):

#define xorSwap(x,y) {(x)=(x)^(y); (y)=(x)^(y); (x)=(x)^(y);}

או כפונקציה:

void xorSwap(int *x, int *y) {
 *x = *x ^ *y;
 *y = *x ^ *y;
 *x = *x ^ *y;
}

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

שימוש בפועל

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

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

ראו גם

• הפרש סימטרי
• XOR לוגי
• רשימה מקושרת של XOR