#computer_system #computer_science

המרות בסיסים

כאשר אנחנו רושמים מספר אנו למעשה עושים שימוש במקדמים ובסיסים. כמו בפולינומים. למשל, הרישום של המספר $102$ הוא

1 \cdot 100 + 0 \cdot 10 + 2 \cdot 1

ניתן לראות שזהו פולינום ריבועי כאשר $x = 10$ כלומר

p (x) = a x^{2} + b x + c x^{0}

p (10) = a 10^{2} + b 10 + c = a 100 + b 10 + c

וכעת אנחנו יודעים ש $a = 1, b = 0, c = 2$ ונקבל את הדרוש. כעובדים עם בסיסים אנחנו תמיד נבין ש $x$ ב״פולינום״ הוא קבוע וערכו הוא כערך הבסיס והמקדמים יכולים להיות טבעיים ושייכים ל $[0, b - 1]$ כאשר $b$ הוא הבסיס.

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

deciaml- בסיס 10 הנפוץ והידוע.
binary- בסיס 2, הספרות הם $0, 1$ .
octal- בסיס 8 והספרות הן $0 - 7$ . הסימון שלו הוא מוביל $0$ למשל $0146$ .
hexadecimal - בסיס 16, הספרות הן $0 - f$ . מסומן על ידי $0 x$ . בגלל שבבסיס הזה אנחנו עברנו את 10 כספרה, עלינו להוסיף אותיות שמייצגות את המספרים מ 10 עד 15 כספרות. לכן A-F מייצגות את המספרים הנ״ל כספרות.

הבחנה

כל ההמרות שנראה מיוחסות למספרים unsigned אבל עבור מספרים עם סימן ההמרות דומות

Unsigned - המרה מכל בסיס ל decimal

האלגוריתם המרה הוא מאוד פשוט.
עבור בסיס $b$ ומספר $x$ המיוצג בבסיס הזה. נסמן את אותו כפולינום המיוצג בבסיס $b$

x = \sum_{i = 0}^{n} a_{i} b^{i}

כאשר $n$ הוא מספר הספרות ו $a_{i} \in {0, 1, \dots, b - 1}$ . לשם הנוחות נגדיר את קבוצת הספרות כקבוצה סדורה, כלומר הסדר של איברי הקבוצה הוא לפי יחס הסדר בינהם , בהתחלה הכי קטן ובסוף הכי גדול.
נגדיר $C : b \to d$ פונקציית המרה של ספרות בבסיס $b$ לבסיס $d$ כלומר, decimal באופן הבא

C (x) = (index of x in b) - 1

כלומר המיקום של $x$ בקבוצה הסדורה, אם ניקח למשל את $E$ בבסיס hexadecimal המיקום שלו בקבוצה $h e x = {0, 1, 2, \dots, E}$ יהיה $15$ וערכו הוא אכן $15 - 1 = 14$ .
כמו כן אנחנו יודעים שערכו של $b$ בבסיס עשרוני הוא $| {0, 1, 2, \dots, b - 1} |$ . כעת האלגוריתם מעבר לבסיס 10 יעבוד כך

הפעל $C$ על כל מקדמי הפולינום של $x$
החלף את ערכי הפולינום בערכים המתאימים ב $C$ (נשים לב שזאת פונקצייה הפיכה, נדבר על ההופכיות בהמשך)
החלף את $b$ בערכו הדסימלי
חשב.

למשל:
א) עבור $1100110$ בבסיס בינארי, נקבל

2^{6} \cdot 1 + 2^{5} \cdot 1 + 2^{4} \cdot 0 + 2^{3} \cdot 0 + 2^{2} \cdot 1 + 2^{1} \cdot 1 + 2^{0} \cdot 0 = 102

נשים לב שהחזקה היא המיקום של הספרה כאשר תחילת הספירה היא מ $0$ .

ב) עבור $0 x 66$ נקבל

f^{1} \cdot 6 + f^{0} \cdot 6 = 16^{1} \cdot 6 + 16^{0} \cdot 6 = 96 + 6 = 102

Unsigned - המרת decimal לבסיס כלשהו

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

כל עוד לא הגענו למחלק $0$
- בצע חלוקה מירבית של המספר העשרוני לפי הבסיס הרצוי
- לחילוק הבא העבר את התוצאה ללא שארית
- שמור את השארית.

השאריות בסדר הפוך זה המספר הרצוי .

דוגמה 1:
נייצג את $103$ בבסיס $8$ .

\frac{103}{8} = 12 | 7

כלומר 12 עם שארית 7.

\frac{12}{8} = 1 | 4

כלומר $1$ עם שארית $4$

\frac{1}{8} = 0 | 1

כלומר $0$ עם שארית $1$ .

ניקח את השאריות בסדר הפוך ונקבל ש $0147$ זה המספר.

דוגמה 2:
נחשב את $8$ בבסיס בינארי.

שארית	שלם
0	8
0	4
0	2
1	1
	0

כלומר בייצוג בינארי המספר הוא $1000$

מעברי בסיסים נפוצים

Bin -> Hex ו Hex-> Bin

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

מבינארי להקס - נוכל פשוט לחלק את הייצוג הבינארי לרביעיות (מימין לשמאל ואם נשאר עודף לרפד באפסים). כל 4 ספרות כעת נמיר לספרה בבסיס 16.

לדוגמה

00101110

נחלק לספרות $1110, 0010$ וכל אחד כבר אנחנו יודעים לחשב בנפרד ונקבל $2 e$ .

טיפ להמרה מהירה

תמיד ניעזר במספרים שקל לייצג עם חזקות של $2$ למשל אנחנו יודעים עבור המקרה הנ״ל ש $1000 = 2^{3}$ בבסיס $10$ (חשוב לשים לב שמתייחסים למספר כמו פולינום כלומר האינדקס הראשון מתחיל מ $0$ ) ולכן זה שקול ל $8$ . כדי להגיע ל $110$ הנותרים בדוגמה שלנו אנחנו יודעים שצריך להוסיף עוד $2^{2} + 2^{1}$ שזה בעצם $6$ כלומר סך הכל מחברים $8 + 6$ בבסיס $10$ שזה $14$ בבסיס $16$ כלומר $e$

הקס לבינארי - כל תו בהקס נמיר ל $4$ ביטים ונחליף את התו בייצוג הבינארי המתאים.

Bin -> Oct ו Oct-> Bin

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

כל שאר הייצוגים יידרשו לרוב להשתמש באלגוריתם מעבר לעשרוני או בינארי ואז לבסיס אחר