Binary to Decimal
ניתנת לך מחרוזת s שמייצגת מספר לא שלילי בבינארית, באמצעות התווים 0 ו-1 בלבד. החזר את ערכו של המספר כמספר שלם רגיל. למחרוזת אין אפסים מובילים, למעט המספר אפס, שמיוצג באמצעות התו היחיד 0.
פונקציה
- sstring
- הספרות הבינאריות של המספר
- מחזירהinteger
- הערך של s כמספר שלם
אילוצים
1 ≤ s.length ≤ 31sמכיל רק0ו־1.sמתחילה ב־1, אלא אםsהיא"0".- קרא בעצמך את הספרות במקום לקרוא להמרת בסיס מובנית.
דוגמאות
- קלט
- s = "1101"
- פלט
- 13
- הסבר
- בקריאה מימין, המקומות שווים 1, 2, 4 ו-8. ב-
1101יש 1 במקומות של 8, 4 ו-1, ו-8 + 4 + 1 = 13.
- קלט
- s = "0"
- פלט
- 0
- הסבר
- ל־
0בודד אין 1 באף מקום, ולכן ערכו הוא0.
- קלט
- s = "10000000"
- פלט
- 128
- הסבר
- ל־1 היחיד יש שבעה 0 מימינו, ולכן הוא נמצא במקום ששווה
2^7 = 128.
+16 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר לקרוא מספר הכתוב בכל בסיס מ־2 עד 16 באמצעות אותה לולאה, כאשר האותיות a עד f מייצגות את הספרות 10 עד 15?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
בכתיב עשרוני, הספרות של
347שוות ל־300, ל־40 ול־7. מה הערך של כל ספרה בינארית?הספרה הבינארית הימנית ביותר שווה ל־1, ובכל צעד שמאלה ערך המקום מוכפל פי שניים: 1, 2, 4, 8 וכן הלאה. המספר הוא סכום ערכי המקומות שבהם מופיעה הספרה 1.
אפשר להימנע מחישוב חזקות: קראו משמאל, ולכל ספרה הציבו את הערך המצטבר כמכפלה של עצמו בשתיים ועוד אותה ספרה. לאחר הספרה האחרונה, הערך המצטבר הוא התשובה.
פתרון
כל ספרה בינארית מייצגת חזקה של שתיים, שנקבעת לפי המרחק שלה מהקצה הימני. אפשר לחבר את החזקות האלה מימין, או לקרוא את המחרוזת משמאל ולהכפיל את הערך בכל שלב. לולאת ההכפלה לעולם אינה מחשבת חזקה, והיא אותה לולאה שמשמשת לקריאת טקסט עשרוני, עם 2 במקום 10.
חברו את ערכי המקום מימין
האינטואיציה
הספרה הימנית ביותר שווה 1, הבאה אחריה 2, ואז 4, 8 וכן הלאה, כשהערך מוכפל בכל צעד שמאלה. המספר הוא סכום ערכי המקום שבהם מופיעה 1. לכן עברו מהתו האחרון לראשון, שמרו את ערך המקום הנוכחי ב־power, והוסיפו אותו בכל פעם שהספרה היא 1.
עבור 1101 תפגשו את הספרות 1 (הוסיפו 1), 0 (דלגו על 2), 1 (הוסיפו 4) ו־1 (הוסיפו 8), והסכום הוא 13. עוברים על כל ספרה פעם אחת, לכן הלולאה פועלת בזמן O(n) ומשתמשת בזיכרון של שני מספרים.
שימו לב לגודל של power. עבור מחרוזת בת 31 ספרות, הוא מגיע ל־2^30 בספרה האחרונה ואז מוכפל פעם נוספת ל־2^31, ערך שאינו נכנס למספר שלם signed בן 32 סיביות. שמרו את power במשתנה בן 64 סיביות, או הפסיקו להכפיל אחרי הספרה האחרונה.
אלגוריתם
- הגדר את
total = 0ואתpower = 1. - עבור על המחרוזת מהתו האחרון שלה ועד לתו הראשון.
- אם התו הוא
1, הוסף אתpowerאלtotal. - הכפל את
powerלפני שתזוז מקום אחד שמאלה. - החזר את
total.
def toDecimal(s):
total = 0
power = 1 # the place value of the rightmost digit
for i in range(len(s) - 1, -1, -1):
if s[i] == "1":
total += power
power *= 2
return totalכפול והוסף משמאל
האינטואיציה
קרא את המחרוזת משמאל ושמור ב־value את המספר שמיוצג על ידי הספרות שנקראו עד כה. הוספת ספרה בינארית נוספת מזיזה את כל הספרות הקודמות מקום אחד שמאלה, וכך מכפילה את ערכן, ואז מוסיפה את הספרה החדשה. לכן בכל שלב מבצעים value = value * 2 + digit.
עבור 1101, הערך של value הוא 1, ואז 1 * 2 + 1 = 3, ואז 3 * 2 + 0 = 6, ואז 6 * 2 + 1 = 13. כל קידומת של המחרוזת היא מספר בינארי קטן יותר, והלולאה שומרת בדיוק את המספר הזה, כך שאחרי הספרה האחרונה הוא מכיל את הערך כולו.
הערך לעולם אינו עולה על התוצאה הסופית, ולכן עבור מחרוזת בת 31 ספרות הוא נשאר בטווח של 2^31-1, ומספר שלם בן 32 סיביות מספיק. הספרה היא קוד התו פחות הקוד של '0', וכך '1' הופך ל־1 ו־'0' הופך ל־0. זו הדרך המקובלת לנתח מספר מתוך טקסט בכל בסיס.
אלגוריתם
- הגדר את
value = 0. - עבור כל תו, משמאל לימין, המר אותו לספרה על ידי הפחתת הקוד של
'0'. - הגדר את
value = value * 2 + digit. - החזר את
value.
def toDecimal(s):
value = 0
for ch in s:
# Shift the digits read so far one place left, then add the new one.
value = value * 2 + (ord(ch) - ord("0"))
return value
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מכיוון המעבר או מסוג הספרה.
- מתן ערך המקום 1 לספרה השמאלית ביותר. ערכי המקום מתחילים בקצה הימני, לכן יש לעבור מהתו האחרון, או להשתמש בלולאת הכפלה משמאל.
- חיבור התו במקום הספרה. בשפות רבות
'1'הוא המספר 49, ולכןvalue * 2 + '1'גדול מדי. יש לחסר תחילה את'0'. - חריגה מערך המקום. הכפלת
powerלאחר הספרה ה־31 נותנת2^31, שגורם לגלישה או לקריסה במספר שלם בן 32 סיביות. - חישוב כל ערך מקום באמצעות פונקציית חזקה בנקודה צפה. ב־C, ב־C++ וב־Java, הפונקציה
pow(2, k)מחזירה ערך מסוגdouble, ויש להמיר את התוצאה בחזרה למספר שלם.
שאלות נפוצות4
איך ממירים מבינארי לעשרוני?
תן לכל ספרה ערך מיקום: 1 עבור הספרה הימנית ביותר, אחר כך 2, 4, 8 וכן הלאה לכיוון שמאל. חבר את ערכי המיקום של הספרות שהן 1. עבור 1101, זה 8 + 4 + 1 = 13.
למה הכפלת הערך עובדת?
כתיבת ספרה נוספת בסוף מספר בינארי מזיזה כל ספרה קודמת מקום אחד שמאלה, וכל מקום שווה פי שניים מהמקום שמימינו. לכן הערך הקודם מוכפל, והספרה החדשה מוסיפה 0 או 1. חזרה על התהליך הזה מהספרה הראשונה ועד האחרונה בונה את המספר השלם.
מהי סיבוכיות הזמן של המרת מספר בינארי לעשרוני?
שתי הלולאות עוברות על כל אחד מ־n התווים פעם אחת, ולכן זמן הריצה שלהן הוא O(n). הן שומרות רק מספר אחד או שניים, ולכן נדרש להן שטח נוסף של O(1). עבור מחרוזת בת 31 תווים, מדובר ב־31 צעדים.
האם אפשר להמיר מבינארי לעשרוני באמצעות הזזות ביטים?
כן. value << 1 מכפיל את הערך, ו-| digit מגדיר את הביט הנמוך ביותר, כך ש-value = (value << 1) | digit עושה את אותו הדבר כמו value * 2 + digit. צורת ההזזה מבהירה שמזיזים ביטים, ואילו הצורה האריתמטית פועלת גם בבסיסים שאינם 2.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def toDecimal(s):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
s = "1101"
צפוי
13