XOR – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־02:26, 17 בנובמבר 2015

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

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

טבלת אמת

q	p	תוצאה
0	0	0
1	0	1
0	1	1
1	1	0

מהטבלה אפשר להסיק ש (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 תלויה במספר האופרנדים בעלי ערך "אמת": אם יש מספר אי-זוגי של אופרנדים כאלה, התוצאה תהיה "אמת" (truth); אחרת, היא תהיה "שקר" (false).

סימונים

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

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

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

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

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

שימושים

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

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

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

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

A = A XOR B

B = A XOR B

A = A XOR B

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

ראו גם

הערות שוליים

^ http://www.talkingelectronics.com/projects/PICK%20A%20PIC%20Project/XOR-Trick-1.html

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

[1]

@@ שורה 1: / שורה 1: @@
-ב[[אלגברה בוליאנית]], '''או מוציא''' – '''XOR''' (לפי [[האקדמיה ללשון העברית|האקדמיה]], מבוטא: "אֶקְסוֹר"; אך בפי רוב, מקוצר לעתים קרובות ל"קְסוֹר") או '''eXclusive OR''' היא [[פעולה בוליאנית]], אשר תוצאתה "אמת" כאשר אחד ה[[אופרנד|אופרנדים]] שלה, ורק אחד מהם, הוא "אמת". פעולה זו היא מקרה פרטי של הפעולה [[הפרש סימטרי]] בקבוצה <math>\ \{0,1\}</math>. כאשר האופרטור מורחב למספר אופרנדים גדול משניים, הוא יחזיר אמת כאשר למספר [[אי-זוגי]] של אופרנדים יש ערך אמת. האופרטור הוא [[פעולה קומוטטיבית|קומוטטיבי]] ("חילופי") ו[[פעולה אסוציאטיבית|אסוציאטיבי]] ("קיבוצי").
+ב[[אלגברה בוליאנית]], '''או מוציא''' – '''XOR''' (לפי [[האקדמיה ללשון העברית|האקדמיה]], מבוטא: "אֶקְסוֹר"; אך בפי רוב, מקוצר לעתים קרובות ל"קְסוֹר") או '''eXclusive OR''' היא [[פעולה בוליאנית]] אשר תוצאתה "אמת" כאשר אחד ה[[אופרנד|אופרנדים]] שלה, ורק אחד מהם, הוא "אמת". פעולה זו היא מקרה פרטי של הפעולה [[הפרש סימטרי]] בקבוצה <math>\ \{0,1\}</math>. כאשר האופרטור מורחב למספר אופרנדים גדול משניים, הוא יחזיר אמת כאשר למספר [[אי-זוגי]] של אופרנדים יש ערך אמת. האופרטור הוא [[פעולה קומוטטיבית|קומוטטיבי]] ("חילופי") ו[[פעולה אסוציאטיבית|אסוציאטיבי]] ("קיבוצי").
-או מוציא הוא פעולה המשקפת את המשמעות השכיחה של המילה "או" בחיי היומיום, בשונה המשמעות של '[[או (לוגיקה)|או]]' בלוגיקה. כאשר אדם אומר לרעהו "אחזיר לך את הספר מחר או מחרתיים", הוא מתכוון שיעשה זאת באחד משני המועדים, אך לא בשניהם.
+או מוציא הוא פעולה המשקפת את המשמעות השכיחה של המילה "או" בחיי היומיום, בשונה מהמשמעות של '[[או (לוגיקה)|או]]' בלוגיקה. כאשר אדם אומר לרעהו "אחזיר לך את הספר מחר או מחרתיים", הוא מתכוון שיעשה זאת באחד משני המועדים, אך לא בשניהם.
 == [[טבלת אמת]] ==
@@ שורה 29: / שורה 29: @@
 XOR הוא [[חילופיות|חילופי]]: סדר האופרנדים אינו משנה - התוצאה תישאר זהה לכל סדר.
-באופן כללי, התוצאה של XOR תלויה במספר האופרנדים בעלי ערך "אמת" : אם יש מספר אי-זוגי של אופרנדים כאלה, התוצאה תהיה "אמת" (truth); אחרת, היא תהיה "שקר" (false).
+באופן כללי, התוצאה של XOR תלויה במספר האופרנדים בעלי ערך "אמת": אם יש מספר אי-זוגי של אופרנדים כאלה, התוצאה תהיה "אמת" (truth); אחרת, היא תהיה "שקר" (false).
 == סימונים ==
 ישנם סימונים מתמטיים שונים לפעולת ה-XOR.
-בנוסף לסימון הפעולה כפשוט "XOR", ישנם המסמנים אותו כסימן פלוס ("+"), או סימן פלוס עם שינוי כלשהו, למשל בתוך עיגול ("<math>\oplus</math>"). האחרון נמצא בשימוש כיוון שישנה התאמה ל[[חיבור]] [[מודולו]] 2, כאשר "אמת"=1 ו"שקר"=0.
+בנוסף לסימון הפעולה באופן פשוט כ-"XOR", ישנם המסמנים אותו כסימן פלוס ("+"), או סימן פלוס עם שינוי כלשהו, למשל בתוך עיגול ("<math>\oplus</math>"). האחרון נמצא בשימוש כיוון שישנה התאמה ל[[חיבור]] [[מודולו]] 2, כאשר "אמת"=1 ו"שקר"=0.
 כמו כן, מקובל לסמן את ה-XOR בסימן הוי בשינוי כלשהו, כגון ("<u>&or;</u>"), כיוון שה-XOR היא פעולה נגזרת של ה-[[OR לוגי|OR הלוגי]], אשר בדרך כלל מסומן בוי.
@@ שורה 40: / שורה 40: @@
 סימון מקובל בתכנות הוא סימן הקארה ("^"), כפי שבא לידי ביטוי ב[[C (שפת תכנות)|שפת התכנות C]].
-בדומה, סימונים טקסטואלים שונים נמצאים בשימוש, כגון "EOR", ו"ORR".
+כמו כן נמצאים בשימוש סימונים טקסטואליים שונים, כגון "EOR", ו"ORR".
 == שימושים ==