XOR

באלגברה בוליאנית, או בררני או או מוציא (באנגלית: eXclusive OR ובראשי תיבות: XOR) היא פעולה בוליאנית המקבלת שני אופרנדים ומחזירה אמת כאשר שני האופרנדים שונים^[1]^[2].

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

מבחינה מתמטית פעולה זו היא מקרה פרטי של פעולת הפרש סימטרי בקבוצה $\ \{0,1\}$ . כאשר האופרטור XOR מורחב למספר אופרנדים גדול משניים, הוא יחזיר אמת כאשר למספר אי-זוגי של אופרנדים יש ערך אמת. XOR הוא קומוטטיבי ("חילופי") ואסוציאטיבי ("קיבוצי").

טבלת אמת

טבלת האמת של XOR היא^[1]:

תוצאה	B	A
0	0	0
1	1	0
1	0	1
0	1	1

מהטבלה אפשר להסיק ש (A XOR B) שקול ל:

(A AND NOT B) OR (NOT A AND B)
(A OR B) AND (NOT A OR NOT B)
(A OR B) AND NOT (A AND B)
[(NOT(A AND B) AND NOT[(NOT A) AND (NOT B

חישוב XOR

לביטויים בעלי יותר משני אופרנדים, מפעילים XOR על שני האופרנדים הראשונים, אחר כך מפעילים XOR על התוצאה מקודם ועל האופרנד השלישי, וחוזר חלילה עד האופרנד האחרון. כלומר לחישוב הביטוי (A xor B xor C xor D) מבצעים את סדר הפעולות הבא (לפי סדר הסוגריים): (A xor B) xor C) xor D))).

XOR הוא חילופי: סדר האופרנדים אינו משנה - התוצאה תישאר זהה לכל סדר.

באופן כללי, התוצאה של XOR תלויה במספר האופרנדים בעלי ערך "אמת": אם יש מספר אי-זוגי של אופרנדים כאלה, התוצאה תהיה "אמת" (truth); אחרת, היא תהיה "שקר" (false).

סימונים

ישנם סימונים מתמטיים שונים לפעולת ה-XOR.

בנוסף לסימון הפעולה באופן פשוט כ-"XOR", ישנם המסמנים אותו כסימן פלוס ("+"), או סימן פלוס עם שינוי כלשהו, למשל בתוך עיגול (" $\oplus$ "). האחרון נמצא בשימוש כיוון שישנה התאמה לחיבור מודולו 2, כאשר "אמת"=1 ו"שקר"=0.

כמו כן, מקובל לסמן את ה-XOR בסימן הוי בשינוי כלשהו, כגון ("∨"), כיוון שה-XOR היא פעולה נגזרת של ה-OR הלוגי, אשר בדרך כלל מסומן בוי.

סימון מקובל בתכנות הוא סימן הגג ("^"), כפי שבא לידי ביטוי בשפת התכנות C.

כמו כן נמצאים בשימוש סימונים טקסטואליים שונים, כגון "EOR", ו"ORR".

שימושים

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

בנוסף, אם נפעיל על ערך בינארי פעולת XOR עם עצמו, נקבל תמיד את התוצאה 0 ("שקר"). במספר ארכיטקטורות של מחשבים, זה מהיר וחסכוני יותר להפעיל XOR על הערך הקיים במקום לשמור את הערך הקבוע 0 באוגר ולכתוב אותו לתוך הזיכרון. לכן, הפעלת XOR על ערכים עם עצמם היא אופטימיזציה נפוצה.^[3]

לפעמים משתמשים בפעולת ה-XOR כפונקציית ערבול בהצפנה. שיטת הצפנה אחת המתבססת על XOR, פנקס חד פעמי, הוּכחה מתמטית כלא ניתנת לפיצוח.

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

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

A = A XOR B

B = A XOR B

A = A XOR B

(ראו: אלגוריתם ההחלפה של XOR)

ראו גם

קישורים חיצוניים

מדיה וקבצים בנושא XOR בוויקישיתוף

XOR, באתר MathWorld (באנגלית)

הערות שוליים

^ ¹ ² קראו בכותר - מיקרו-בקרים ושפה עילית - כרך ב, באתר school.kotar.cet.ac.il
^ Eric W. Weisstein, XOR, mathworld.wolfram.com (באנגלית)
^ http://www.talkingelectronics.com/projects/PICK%20A%20PIC%20Project/XOR-Trick-1.html

[:0-1] ¹ ² קראו בכותר - מיקרו-בקרים ושפה עילית - כרך ב, באתר school.kotar.cet.ac.il

[2] Eric W. Weisstein, XOR, mathworld.wolfram.com (באנגלית)

[3] ttp://www.talkingelectronics.com/projects/PICK%20A%20PIC%20Project/XOR-Trick-1.html

[1]

[2]

[3]