Decimal to Binary
ניתן לך מספר שלם לא שלילי n. החזר את הייצוג הבינארי שלו כמחרוזת של 0 ו-1, ללא אפסים מובילים. המספר היחיד שהתשובה עבורו מתחילה ב-0 הוא אפס עצמו, שנכתב "0".
פונקציה
- ninteger
- המספר שיש להמיר
- מחזירהstring
- הספרות הבינאריות של n כמחרוזת
אילוצים
0 ≤ n ≤ 231-1- בנו את המחרוזת בעצמכם במקום לקרוא לפונקציית המרה מובנית.
דוגמאות
- קלט
- n = 13
- פלט
- "1101"
- הסבר
13 = 8 + 4 + 1. במקומות של 8, 4, 2 ו-1 מופיעים1,1,0ו-1, וכך מתקבל1101.
- קלט
- n = 0
- פלט
- "0"
- הסבר
- לאפס אין ביטים מוגדרים, אבל התשובה עדיין צריכה להכיל ספרה אחת, ולכן היא
"0"ולא מחרוזת ריקה.
- קלט
- n = 64
- פלט
- "1000000"
- הסבר
64הוא2^6,1יחיד במקום של ה־64 ואחריו שישה0עבור המקומות מ־32 ועד 1.
+16 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר להמיר את n לכל בסיס בין 2 ל־16 באמצעות אותה לולאה, ולהשתמש באותיות a עד f עבור הספרות שמעל 9?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
איזו ספרה בינארית של
nאפשר למצוא בלי לדעת אף אחת מהאחרות? חשבו על מספרים זוגיים ואי־זוגיים.הספרה האחרונה היא
n % 2. חלוקתnב־2 והשמטת השארית מסירות את הספרה הזאת ומעבירות את הספרה הבאה למקום האחרון.חזור: רשום את
n % 2, ואז חלק אתnבשניים, עד ש-nיהיה 0. הספרות מתקבלות מהנמוכה לגבוהה, לכן הפוך את הסדר שלהן בסוף. לאפס דרושה תשובה משלו.
פתרון
מספר בינארי הוא סכום של חזקות של שתיים, וכל ספרה מציינת אם חזקה מסוימת נכללת בסכום. אפשר לקבוע את הספרות מלמעלה על ידי חיסור חזקות של שתיים, או לקרוא אותן מלמטה כשאריות של חלוקה חוזרת ב־2. לולאת החלוקה היא השיטה המקובלת: אין צורך למצוא תחילה את החזקה הגדולה ביותר, והיא פועלת באותו אופן בכל בסיס.
חסרו חזקות של שתיים מהמספר הגבוה ביותר
האינטואיציה
כך ממירים ביד. מצאו את החזקה הגדולה ביותר של שתיים שנכנסת ב־n; זו הספרה הראשונה, 1. לאחר מכן רדו חזקה אחת בכל פעם. אם החזקה עדיין נכנסת במה שנשאר, כתבו 1 והחסירו אותה; אחרת כתבו 0.
עבור 13, החזקה הגדולה ביותר היא 8. כתבו 1 ונשארים עם 5. לאחר מכן 4 נכנס (1, נשאר 1), 2 לא נכנס (0), ו־1 נכנס (1). הספרות הן 1101. הספרה הראשונה היא תמיד 1, ולכן לא יכול להופיע אפס מוביל.
מציאת החזקה הגדולה ביותר דורשת זהירות. הכפלת power שוב ושוב עד שהוא עובר את n גורמת לגלישה של מספר שלם בן 32 סיביות ברגע ש־n ≥ 2^30, כי החזקה הבאה היא 2^31. הכפלה רק כל עוד power ≤ n / 2 עוצרת בחזקה המתאימה בלי לעבור את n. מספר בן 31 סיביות דורש 31 צעדים, כלומר O(log n).
אלגוריתם
- אם
nהוא0, החזר"0". - התחל עם
powerבערך 1 והכפל אותו כל עודpower ≤ n / 2. - כל עוד
power > 0: אםn ≥ power, הוסף1והחסר אתpowerמ־n; אחרת הוסף0. - חלק את
powerב־2 וחזור על הפעולה. - החזר את הספרות שהוספת.
def toBinary(n):
if n == 0:
return "0"
# Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
power = 1
while power <= n // 2:
power *= 2
bits = []
while power > 0:
if n >= power:
bits.append("1")
n -= power
else:
bits.append("0")
power //= 2
return "".join(bits)חלוקה חוזרת ב־2
האינטואיציה
הספרה הבינארית האחרונה של n מציינת אם n זוגי או אי־זוגי, והיא n % 2. חלוקה ב־2 והשמטת השארית מזיזות כל ספרה מקום אחד ימינה, כך שהספרה הבאה הופכת לאחרונה. חוזרים על כך עד שלא נשאר דבר ואוספים את כל הספרות, מהנמוכה לגבוהה.
עבור 13: בחלוקה של 13 מתקבלת שארית 1, בחלוקה של 6 מתקבלת שארית 0, בחלוקה של 3 מתקבלת שארית 1, ובחלוקה של 1 מתקבלת שארית 1, ואז המספר הוא 0. השאריות לפי הסדר הן 1, 0, 1, 1; בסדר הפוך הן נקראות 1101. הלולאה נעצרת כשהמספר מגיע ל־0, ולכן הספרה הגבוהה ביותר שהיא כותבת היא תמיד 1 ולא מופיע אפס מוביל. אפס עצמו לעולם לא נכנס ללולאה, ולכן הוא זקוק לבדיקה משלו.
בכל שלב המספר נחצה, ולכן ערך בן 31 סיביות דורש 31 שלבים, זמן O(log n), ומחרוזת הספרות דורשת מקום O(log n).
אלגוריתם
- אם
nהוא0, החזר"0". - כל עוד
n > 0, הוסף אתn % 2כספרה והצב אתnעלn / 2, בעיגול כלפי מטה. - הפוך את סדר הספרות, כי הן התקבלו מהנמוכה לגבוהה.
- החזר אותן כמחרוזת.
def toBinary(n):
if n == 0:
return "0"
bits = []
while n > 0:
# The remainder is the lowest bit that is left.
bits.append(str(n % 2))
n //= 2
# The bits came out lowest first, so turn them around.
bits.reverse()
return "".join(bits)
מלכודות ומקרי קצה
הלולאה קצרה, ורוב התשובות השגויות נובעות משני הקצוות שלה.
- החזרת מחרוזת ריקה עבור
0. לולאת החלוקה אינה מתבצעת עבור אפס, לכן יש לבדוק אותו קודם. - שוכחים להפוך את הסדר. השאריות מתקבלות מהספרה הנמוכה ביותר לראשונה, לכן
6מתקבל כ-011במקום110. - שימוש ב-
/בשפה שבה הוא מחזיר שבר, כמו JavaScript, Lua או PHP.13 / 2חייב להפוך ל-6, לכן יש לעגל כלפי מטה או להשתמש בחלוקה של מספרים שלמים. - בניית החזקה הגדולה ביותר על ידי הכפלה עד שעוברים את
n. עבורn = 2^31-1, החזקה הבאה,2^31, אינה נכנסת למספר שלם בן 32 סיביות. - הקצאת זיכרון קטן מדי ב-C. מספר בן 31 סיביות זקוק ל-31 תווים ועוד לתו המסיים
'\0'.
שאלות נפוצות4
איך ממירים מספר עשרוני לבינארי?
חלקו את המספר ב־2 שוב ושוב, ורשמו כל שארית, עד שהמספר מגיע ל־0. קראו את השאריות מהאחרונה לראשונה. עבור 13 השאריות הן 1, 0, 1, 1, ולכן 13 בבינארי הוא 1101.
למה קוראים את השאריות בסדר הפוך?
החלוקה הראשונה ב־2 אומרת לך אם המספר אי־זוגי, כלומר מהי הספרה הבינארית האחרונה. כל חלוקה מאוחרת יותר חושפת את הספרה הבאה משמאל. לכן השאריות מתקבלות מהספרה הנמוכה ביותר תחילה, ואתה הופך את הסדר שלהן כדי לכתוב את המספר בדרך המקובלת.
מהי סיבוכיות הזמן של המרת מספר עשרוני לבינארי?
כל צעד מחלק את המספר ב-2, ולכן הלולאה רצה פעם אחת לכל ספרה בינארית, כלומר בערך log2(n) פעמים. זה זמן של O(log n), ומחרוזת התשובה תופסת מקום של O(log n). עבור מספר שלם בן 32 סיביות, מדובר בעד 31 צעדים.
האם אפשר להמיר לבינארי באמצעות פעולות ביטיות במקום חילוק?
כן. n & 1 מחזיר את הביט הנמוך ביותר, ו-n >> 1 מסיר אותו, וזה שקול ל-n % 2 ול-n / 2 עבור מספרים לא שליליים. הלולאה וההיפוך נשארים זהים. קל יותר להסביר חלוקה, ואילו גרסת ההזזה נפוצה בקוד ברמה נמוכה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def toBinary(n):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
n = 13
צפוי
"1101"