כתוב תוכנית אשר כוללת שני משתנים שמכילים שני ערכים מספריים שלמים. התכנית מחליפה את תוכנם של שני המשתנים זה בזה מבלי לעשות שימוש במשתנה עזר?

אותה השאלה רק בפעולות על ביטים.

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

(:

לכותב השאלה, תוכל למצא דיונים בנושא זה בפורום DC
הנה קישור לפורום, תריץ חיפוש (פעיל רק בלילה עד 12 בבוקר):
http://www.fresh.co.il/dcforum/dcbo...nf=ComputersPro

[ זיו ]
[ fat fish ]

a = a Xor b

b = b Xor a

a = a Xor b

ואיך היא נקראת בפסקל? אם יש אותה כמובן..

אשכר

פעולת xor (exclusive or) פעולה שמבוצעת כל ביטים. פעולה זו פעולה בינארית אשר לוקחת שני ביטים:

קוד:

 1 xor 1 = 0
 0 xor 0 = 0
 1 xor 0 = 1
 0 xor 1 = 1
 

הגדרת הפעולה xor:

לפני שנמשיך, חשוב לתאר את הפעולה הזו בדרך מילולית שתעזור לנו להבין למה הקוד ההוא פעל.
אם נסתכל למשך יותר משבריר שניה על הטבלה נראה ש-xor בודקת האם שני הפרמטרים שלה
זהים או שונים. אם הם זהים היא מחזירה 0 ואם הם שונים היא מחזירה 1.

השלב הבא הוא להבין מהי משמעות הפעולה xor עבור משתנים שונים בקוד שלנו, לאו דווקא ביטים.
המשמעות היא פשוטה מאוד והגיונית מאוד, מבוצע xor בין כל שני ביטים במקום מסויים והתוצאה
היא ערך ה-xor במשתנה היעד.
לדוגמה:

מבצעים xor של הביט הראשון בפרצטר הראשון עם הביט הראשון בפרמטר השני, וזהו הביט
הראשון בתוצאה. מבצעים xor של הביט השני בפרצטר הראשון עם הביט השני בפרמטר השני,
וזהו הביט השני בתוצאה, וכך הלאה:

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

עכשיו, הקוד:

עכשיו בואו ננתח את הקוד בהתאם לארבעת המצבים השונים האפשריים עבור ערכים תחיליים
של שני הפרמטרים, A ו-B:
נתחיל מ-B=1, ונראה מה הולך פה. אם גם A=1, אז אחרי השורה הראשונה A=0; אחרי השורה
השניה B=1; ואחרי השורה השלישית שוב A=1. אם A=0 אז אחרי השורה הראשונה A=1; אחרי
השורה השניה B=1; ואחרי השורה השלישית A=0.
אם נעשה את אותה בדיקה עבור שני המקרים האחרים נראה שהקוד באמת "מחליף" את הערכים
של שני הפרמטרים, ועפ"י הגדרת הפעולה xor עבור משתנים השונים מביט-בודד, אנחנו רואים
שזה יפעל תמיד.

הקונץ הזה פועל בגלל שxor היא פעולה שגורמת לכך שאם A xor B = C כאשר A,B,C הם סיבית בודדת (או ביט בודד איך שבא לך)
C xor A = B
וגם
C xor B = A

היות וביצוע xor על רצף של סיביות (כמו כל משתנה שמכיל מספר שלם) היא ביצוע xor על כל אחת מהסיביות אז זה תקף גם כאשר A,B,C הם רצפים של סיביות

a,b
a=a+b
b=a-b
a=a-b

שיטת ה-xor עדיפה כי הגישה הזו יוצרת גלישה.
מבחינה מתמטית-נטו היא מצויינת; מבחינה מעשית היא פועלת רק בחלק מהמקרים - כלומר, שגויה מבחינה תכנותית.

אוקיי, אבל לא הבנתי למה השיטה הזו שגויה מבחינה תכנותית

הרעיון בתכנות הוא שתוכנה מסויימת פועלת תמיד:
התכנה פועלת על כל מחשב
בכל זמן
בכל מצב
ו.....עבור כל קלט

השיטה ה"מתמטית" לא פועלת עבור כל קלט.
אם A ו-B מספיק גדולים תהיה גלישה.
חוק אצבע: תכנית שפועלת רק לפעמים אינה תכנית טובה.

(:

אלכס מתכוון לדבר הבא:
משתנה מסוג int הוא בגודל 16 סיביות (נלך על unsign בשפת C) ולכן אתה יכול להזין לתוכו מספרים עד גודל של 65,000 בערך.
בהנחה ותנסה את בתהליך המתמטי על זוג מספרים שערכם גדול מ-65,000 (לדוגמה 50,000 ו-35,420) החיבור שלהם (מהצורה שהצגת a=a+b) יהיה יותר ממה שהמשתנה מסוגל להחזיק ולכן התוצאה שתתקבל תהיה שגוייה עקב זליגה.

פעולות על סיביות (XOR) רק מחליפות את מצב הסיביות ולא מבצעות פעולה העלולה ליצור זליגה (לא!! כל פעולה על סיביות, רק XOR ו- NOT לא גורמות זליגה).

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

[ זיו ]
[ fat fish ]

סביר להניח שלמרות שתהיה גלישה התוצאה הסופית תהיה נכונה.
(המספר ב-a בהתחלה יראה כמו מספק שלילי מוזר בדוגמה שלך, אבל אחרי 3 השורות, הוא יהיה שווה ל-b ההתחלתי)
אלא מה? -גם אם זה פועל, עצם זה שיש שם שגיאת גלישה, מראה שמשהו פה לא בסדר...