אי-שוויון עם XOR

עריסטו

Active member
זה תרגיל מקורי :geek:
הוכיחו:
אם a, b, c הם מספרים טבעיים כך ש:
a XOR b < c וגם a XOR c < b
אז מתקיים גם אי-השוויון השלישי:
b XOR c < a
כאשר XOR זה bitwise exclusive or, למשל
zzz 3 XOR 5 = 6
 

Lucifer LightBringer

Well-known member
מה 3xor5=3+5-2? חיפשתי bitwise exclusive אבל לא הבנתי איך זה מתקשר לפעולה פה?

חזקה בבינארית?
 

עריסטו

Active member
כדי לחשב XOR של שני מספרים טבעיים כותבים אותם בבסיס 2 ומחשבים XOR בכל עמודה בנפרד, כאשר
zzz 0 XOR 0 = 1 XOR 1 = 0
zzz 0 XOR 1 = 1 XOR 0 = 1
למשל כדי לחשב את zzz 5 XOR 22
101
10110
--------------
10011
לכן zzz 5 XOR 22 = 19
הבעיה היא להוכיח שאם
a xor b < c
וגם
a xor c < b
אז
b xor c < a
 

Lucifer LightBringer

Well-known member
אז אפשר לרשום לפי הייצוג הבינארי axor b= sum a_i*2^i xor sum b_i*2^j כאשר המקדמים בסכום הם אפסים או אחדים.
נשים לב שקיים d טבעי כך שמתקיים שוויון a xor b xor d1 =c
וקיים מספר טבעי d2 כך ש- a xor c xor d2=b.

יש גם חיסור בבינארי לא כך? זה פשוט שקול ל"חיבור" XOR.
בעיקרון קיימים נראה לי מספרים טבעיים d1,d2 כך ש- a xor b xor d1=c
a xor c xor d2=b
מקבלים ש- a xor a xor b xor d1 xor d2=b
השאלה היא למה a xor a שווה?
אם זה 1 או 0 זה טריוויאלי.

האמת עבור a xor a אני לא בטוח למה זה שווה.

דרך אגב ממה שאני זוכר כשיש לך 1+1 אז אכן באגף הראשון זה 1 אך בשני מתקבל 1.

כלומר אם אני לא טועה זה צריך להיות בדוגמא שלך: 101+10110=11011 לא כפי שקיבלת 10011.
 

hada12

Member
אז אפשר לרשום לפי הייצוג הבינארי axor b= sum a_i*2^i xor sum b_i*2^j כאשר המקדמים בסכום הם אפסים או אחדים.
נשים לב שקיים d טבעי כך שמתקיים שוויון a xor b xor d1 =c
וקיים מספר טבעי d2 כך ש- a xor c xor d2=b.

יש גם חיסור בבינארי לא כך? זה פשוט שקול ל"חיבור" XOR.
בעיקרון קיימים נראה לי מספרים טבעיים d1,d2 כך ש- a xor b xor d1=c
a xor c xor d2=b
מקבלים ש- a xor a xor b xor d1 xor d2=b
השאלה היא למה a xor a שווה?
אם זה 1 או 0 זה טריוויאלי.

האמת עבור a xor a אני לא בטוח למה זה שווה.

דרך אגב ממה שאני זוכר כשיש לך 1+1 אז אכן באגף הראשון זה 1 אך בשני מתקבל 1.

כלומר אם אני לא טועה זה צריך להיות בדוגמא שלך: 101+10110=11011 לא כפי שקיבלת 10011.
a xor a = 0
 

Lucifer LightBringer

Well-known member
חזור להגדרה של XOR ותראה שזה אותו דבר.
אז זה לא חיבור בינארי ממה שאני מכיר.
טוב אז a XOR a=0 ומפה מקבלים בהכרח ש- d1 xor d2=0
ואז את a xor c xor d=b נעשה קסור עם b ו-a ונקבל: a xor a xor c xor d xor b= a=b xor c xor d, ולכן a> bxor c.

נשים לב ש- a xor 0=a.
רק צריך להוכיח שאם d1 xor d2=0 אזי d1=d2 וההוכחה פשוטה נניח אחרת למשל ש-d1>d2 אזי קיים d טבעי כך ש- d1=d2 xor d ניקח קסור עם d ונקבל: d1=d2xor d xor d=d2 xor 0-=d2 וזה בסתירה לכך שהם לא שווים.
 
למעלה