משתמש:SGVB/משלים ל-2

שיטת המשלים ל-2 היא שיטה לייצוג מספרים עם סימן בבסיס בינארי. בשיטה זאת הסיבית הגבוהה ביותר (MSB - Most Significant Bit) מייצגת את הסימן של המספר (חיובי או שלילי) ושאר הספרות מייצגות את המספר. שיטה זו מקובלת במחשבים לייצוג בינארי של מספרים שעשויים להיות שליליים, כיוון שקל יחסית לחשב את ערך המספר וכן לבצע עליו פעולות בסיסיות.

מוטיבציה

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

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

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

ייצוג

באמצעות $n$ סיביות ניתן לייצג לכל היותר $2^{n}$ ערכים שונים. נניח שנתונות $n$ סיביות והמטרה היא לייצג את הערכים בתחום $[-2^{n-1},2^{n-1}-1]$. לכל מחרוזות בינארית באורך $n$ ישנו תרגום טבעי למספר בתחום $[0,2^{n}-1]$ שהוא פשוט הערך של המחרוזת כמספר בבסיס 2. בחשבון מודולרי מודולו $2^{n}$, לכל מספר $x$ יש מספר הופכי $y\equiv -x{\pmod {2^{n}}}$ כך ש $x+y\equiv 0{\pmod {2^{n}}}$. קל לראות שהמספר $y=n-x$ עונה על ההגדרה הזו, כיוון ש $x+(n-x)\equiv n\equiv 0{\pmod {2^{n}}}$.

לכן, מחרוזת בינרית בתחום $[0,2^{n-1}-1]$, תייצג את הערך שלה, אבל על כל מחרוזת שהערך שלה הוא בתחום $[2^{n-1},2^{n}-1]$, תייצג את ההופכי לערך שלה.

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

בשיטה משתמשים בייצוג הרגיל (ללא סימן) של מספרים בתחום מסוים, למשל מספרים בני 4 ביטים, "חותכים" את החלק העליון של התחום, ומדביקים אותו אל החלק התחתון, באותו סדר. כלומר, אם בייצוג בינארי רגיל המספרים הגבוהים ביותר הם 8-15, בשיטת המשלים ל-2 הייצוג שמשמש את המספרים האלה ישמש עבור המספרים שבין מינוס 8 לבין מינוס 1, באותו סדר. הקידוד עבור 8 (1000) ישמש עבור קידוד מינוס שמונה (16-8=8), הקידוד עבור 9 (1001) ישמש עבור מינוס 7 (16-9=7), וכן הלאה עד הקידוד עבור 15 (1111) שישמש עבור מינוס 1 (16-15=1). כלומר הקידוד עבור 2 בחזקת מספר הביטים פחות X, הוא הקידוד עבור מינוס X.

על מנת לייצג מספר בן n סיביות בשיטת המשלים ל-2 יש להפריד את הסיבית השמאלית ביותר משאר המספר.

כאשר ישנם n סיביות, ניתן לייצג כל x בטווח $-2^{n-1}\leq x\leq 2^{n-1}$ .

מספרים חיוביים מיוצגים על ידי n-1 הספרות הימניות של המספר בייצוג בינארי רגיל, הסיבית השמאלית ביותר היא 0 ומשמעותה שהמספר חיובי. ניתן לייצג רק מחצית מכמות המספרים החיוביים האפשריים בייצוג ללא סימן. בהתאם, במספרים שליליים הסיבית השמאלית ביותר היא 1 ומציינת שהמספר הוא שלילי.

מספר בינארי	ייצוג עשרוני כאשר המספר הוא ללא סימן	ייצוג עשרוני בשיטת המשלים ל-2
0111	7	7
0110	6	6
0101	5	5
0100	4	4
0011	3	3
0010	2	2
0001	1	1
0000	0	0
1111	15	1-
1110	14	2-
1101	13	3-
1100	12	4-
1011	11	5-
1010	10	6-
1001	9	7-
1000	8	8-

חישובים

על מנת להמיר מספר שלילי למספר המיוצג בשיטת המשלים ל-2 יש לחשב את ערכו המוחלט של המספר, להמיר את הערך המוחלט לייצוג בינארי, להפוך את כל הסיביות (1 ל-0 ו-0 ל-1) ולהוסיף 1.

נמיר לדוגמה את המספר 17-
צעד ראשון: נמיר את ערכו המוחלט של 17- למספר בייצוג בינארי (17 = 0001 0001)
צעד שני: נהפוך את כל הסיביות (1110 1110)
צעד שלישי: נוסיף 1 (1111 1110 = 17-)

חיבור

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

לדוגמה: 2 = (3-) + 5

0000‎ 0101	=	5+
1111‎ 1101 +	=	3-
0000‎ 0010	=	2+

חיסור

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

לדוגמה: (5-) = 12 - 7

ראשית נמיר את 12- בשיטת המשלים ל-2 (0100 1111) ולאחר מכן נבצע:

0000‎ 0111	=	7+
1111‎ 0100 +	=	12-
1111‎ 1011	=	5-

פיתוח השיטה

משמעות ההשלמה ל-2 היא שכל הספרות הרגילות עד לספרה השמאלית ביותר מוכפלות ב-2 בחזקת מיקומן, מלבד לספרה השמאלית ביותר שמוכפלת במינוס 2 בחזקת מיקומה, למשל בייצוג השלמה ל-2:

$\ 101001=2^{0}+2^{3}-2^{5}=-23$

והרי כזכור 23 בבסיס בינארי הוא 010111:

$\ 010111=2^{0}+2^{1}+2^{2}+2^{4}+(-2^{5}*0)=23$

אכן ניתן לראות שאם נהפוך את כל הספרות, ונוסיף אחד, נקבל את המוצג לעיל.
כעת, דרך אחת להסתכל על הסיבה לכך שהיפוך הספרות (השלמה ל-1 או יותר נכון Ones' Complement) ולאחר מכן הוספת 1 מייצר את ההשלמה ל- 2 של המספר שאיתו מתחילים, נובעת מהביטוי הבא:

$\ 2^{n}=2^{n-1}+2^{n-2}+...+2^{1}+2^{0}+1$

במקרה שלקחנו למעלה, עבור 23, n=5. כעת ניתן לייצג את 23 בשתי דרכים:

$\ 2^{5}-2^{3}-1=2^{0}+2^{1}+2^{2}+2^{4}$

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

$\ 010111=2^{0}+2^{1}+2^{2}+2^{4}+(-2^{5}*0)=23$

ועכשיו אם נהפוך את כל הספרות:

$\ 101000=2^{3}+(-2^{5}*1)$

וראינו לפי הפיתוח שחסר אחד כדי שנקבל 23-. לכן מוסיפים אחד!

$\ 101001=1+2^{3}+(-2^{5}*1)=-23$

ראו גם

• משלים ל-1

[[קטגוריה:קידוד נתונים]]