Steps to Reduce a Number to Zero

Q: מהי סיבוכיות הזמן של הפחתת מספר לאפס?

הרצת התהליך אורכת זמן O(log n) , כי לפחות בכל צעד שני המספר נחצה לשניים: 61 צעדים עבור n = 2^31 - 1 . ספירת הספרות הבינאריות באמצעות הוראות סיביות מובנות היא O(1) .

Q: איזה מספר הקטן מ־2^31 דורש את מספר הצעדים הגדול ביותר?

2^31 - 1 , כלומר שלושים ואחד מופעים של 1 בייצוג בינארי. נדרשות לו 31 פעולות חיסור ו- 30 פעולות חלוקה ב-2, ובסך הכול 61 צעדים. אין מספר קטן יותר שיש בו מספר רב כל כך של ספרות ומספר רב כל כך של מופעי 1 בו-זמנית.

Q: למה חלוקה בשניים זהה להזזה ימינה?

מספר בינארי הוא סכום של חזקות של שתיים. חלוקת מספר זוגי ב־ 2 מורידה כל חזקה באחד, מה שמזיז כל ספרה מקום אחד ימינה ומשמיט את ה־ 0 האחרון. זה מה שעושה n >> 1 , כך שאפשר לכתוב את החלוקה לחצי בשתי הדרכים.

מתחיליםמניפולציית ביטים מתמטיקה וסימולציה

+10

התחילו ממספר שלם לא שלילי n והחילו שוב ושוב כלל אחד עד שהוא מגיע ל־0: אם המספר זוגי, חלקו אותו ב־2; אם הוא אי־זוגי, החסירו ממנו 1. כל החלה של הכלל היא צעד אחד. החזירו את מספר הצעדים שנדרשים.

פונקציה

numberOfSteps(n: integer) → integer

ninteger: המספר ההתחלתי
מחזירהinteger: מספר הצעדים עד שהמספר מגיע ל־0

אילוצים

0 ≤ n ≤ 2³¹ - 1

דוגמאות

קלט: n = 14
פלט: 6
הסבר: המספר מתקדם כך: 14 → 7 → 6 → 3 → 2 → 1 → 0: שלוש חלוקות בחצי ושלוש פעולות חיסור, 6 צעדים.

קלט: n = 8
פלט: 4
הסבר: 8 → 4 → 2 → 1 → 0. חזקה של שתיים נחצית שלוש פעמים ונדרשת חיסור אחד בסוף, 4 צעדים.

קלט: n = 123
פלט: 12
הסבר: 123 הוא 1111011 בייצוג בינארי: שבע ספרות ושש ספרות 1. שש הספרות 1 דורשות שש פעולות חיסור, ושש הספרות שמתחת לספרה המובילה דורשות שש פעולות חלוקה ב-2, 12 צעדים.

שאלת המשך

נניח שגם מספר אי־זוגי יכול לגדול ב־1. מהו מספר הצעדים הקטן ביותר הדרוש כדי להגיע ל־0, ואיזו בחירה נכונה עבור 15?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

במערכת בינארית, חלוקה ב־2 משמיטה את הספרה האחרונה, וחיסור 1 ממספר אי־זוגי הופך את ה־1 האחרון שלו ל־0. לכן, עבור n > 0, התשובה היא מספר הספרות הבינאריות ועוד מספר הספרות 1, פחות אחת. גם הפעלה ישירה של הכלל מהירה: לכל היותר 61 צעדים.

הפעל את התהליך

האינטואיציה

הריצו את הכלל וספרו את השלבים. עבור 14 הלולאה עוברת דרך 7, 6, 3, 2, 1 ו-0: שישה שלבים.

חיסור תמיד הופך מספר אי-זוגי לזוגי, ולכן לפחות כל שלב שני הוא חלוקה בחצי. מספר שקטן מ-2^31 מתחלק בחצי לכל היותר 30 פעמים לפני שהוא מגיע ל-1. עם חיסור אחד לפני כל חלוקה בחצי ואחד בסוף, הלולאה רצה לכל היותר 61 פעמים. עבור n = 0 הלולאה אינה רצה כלל והתשובה היא 0.

אלגוריתם

הגדר את steps ל־0.
כל עוד n > 0: אם n זוגי, הגדר את n ל־n / 2, אחרת ל־n-1.
הוסף 1 ל־steps בכל פעם.
החזר את steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

ספירת הספרות הבינאריות

האינטואיציה

בכל צעד מסירים את הספרה הבינארית האחרונה או הופכים 1 סופית ל־0. 14 הוא 1110: חלוקה בחצי נותנת 111, וחיסור מ־111 נותן 110. יש לאפס כל 1 פעם אחת, ולכן נדרשת פעולת חיסור אחת לכל 1. יש להסיר כל ספרה, באמצעות חלוקה בחצי אחת לכל ספרה, למעט הספרה המובילה: כשנותר רק 1, החיסור שלו כבר נותן 0. לכן התשובה היא length - 1 + ones, ועבור 14 מתקבל 4 - 1 + 3 = 6.

ל־Java, C, C++, Go, Rust ו־Swift יש פונקציות מובנות לשתי הספירות (אפסים מובילים וסיביות שערכן 1), שמתקמפלות להוראות בודדות ברוב המעבדים. שפות אחרות קוראות את הספרות בעזרת % 2 בלולאה של לכל היותר 31 סבבים. יש לטפל תחילה במקרה n = 0: אין בו סיבית שערכה 1 שתעגן את הנוסחה.

אלגוריתם

אם n == 0, החזר 0.
מצא את length, מספר הספרות הבינאריות של n.
מצא את ones, מספר הביטים שערכם 1.
החזר length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

מלכודות ומקרי קצה

שכחת n = 0 בנוסחת הביטים. הביטוי length - 1 + ones נותן -1, וספירת אפסים מובילים של 0 עשויה להיות לא מוגדרת (__builtin_clz(0) ב-C).
סופרים פעולת חצייה עבור הספרה המובילה. החיסור הופך את 1 ל-0, לכן 8 = 1000 דורש 4 - 1 + 1 = 4 צעדים, ולא 5.
כותבים n = (n-1) / 2 עבור מספר אי-זוגי וסופרים צעד אחד. השורה הזאת מבצעת שני צעדים, ולכן התוצאה עבור 14 היא 4 במקום 6.
מבצעים לולאה כל עוד n > 1. כך עוצרים לפני הצעד האחרון, שהופך את 1 ל-0.

שאלות נפוצות3

מהי סיבוכיות הזמן של הפחתת מספר לאפס?

הרצת התהליך אורכת זמן O(log n), כי לפחות בכל צעד שני המספר נחצה לשניים: 61 צעדים עבור n = 2^31 - 1. ספירת הספרות הבינאריות באמצעות הוראות סיביות מובנות היא O(1).

איזה מספר הקטן מ־2^31 דורש את מספר הצעדים הגדול ביותר?

2^31 - 1, כלומר שלושים ואחד מופעים של 1 בייצוג בינארי. נדרשות לו 31 פעולות חיסור ו-30 פעולות חלוקה ב-2, ובסך הכול 61 צעדים. אין מספר קטן יותר שיש בו מספר רב כל כך של ספרות ומספר רב כל כך של מופעי 1 בו-זמנית.

למה חלוקה בשניים זהה להזזה ימינה?

מספר בינארי הוא סכום של חזקות של שתיים. חלוקת מספר זוגי ב־2 מורידה כל חזקה באחד, מה שמזיז כל ספרה מקום אחד ימינה ומשמיט את ה־0 האחרון. זה מה שעושה n >> 1, כך שאפשר לכתוב את החלוקה לחצי בשתי הדרכים.

def numberOfSteps(n):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

n = 14

הפלט הצפוי