החלפה בעזרת 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 זה ייראה כך:

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ים הנ"ל.

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