או אקסקלוסיבי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 טבלת אמת
2 חישוב XOR
3 סימונים
4 שימושים
5 ראו גם

[עריכה] טבלת אמת

q	p	תוצאה
שקר	שקר	שקר
אמת	שקר	אמת
שקר	אמת	אמת
אמת	אמת	שקר

מהטבלה אפשר להסיק ש (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)

[עריכה] חישוב XOR

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

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

[עריכה] סימונים

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

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

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

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

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

[עריכה] שימושים

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

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

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

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

A = A XOR B

B = B XOR A

A = A XOR B

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