החלפה בעזרת XOR
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתכנות, אלגוריתם ההחלפה של XOR הוא אלגוריתם אשר משתמש בפעולה לוגית XOR בכדי להחליף ערכים של שני משתנים, בעלי אותו סוג מידע, וללא שימוש במשתנה עזר זמני. האלגוריתם משתמש בתכונת ההפרש הסימטרי של פעולת הXOR שהינה - A XOR A שווה תמיד ל0 ("שקר"), לכל A.
תוכן עניינים |
[עריכה] האלגוריתם
אלגוריתמים סטנדרטיים להחלפת ערכים של שני משתנים דורשים שימוש במשתנה עזר. למשל, להלן אלגוריתם בסיסי להחלפת שני משתנים - X וY:
- העתק את ערך Y למשתנה העזר
- העתק את ערך X למשתנה Y
- העתק את ערך משתנה העזר למשתנה X
לעומת זאת, אלגוריתם הXOR משחרר את הצורך במשתנה עזר - להלן אלגוריתם ה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 (זהויות לוגיות שניתן להוכיח). ואז -
- 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;
קוד זה ניתן לכתוב גם בצורה של ביטוי אחד, אשר משתמש בתכונה של האסוציאטיביות מימין של ההשמה בC:
x ^= y ^= 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

