Counting Bits

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

הפתרון הטוב ביותר פועל בזמן O(n): כל אחת מ־ n+1 הכניסות נוצרת מכניסה קודמת אחת באמצעות פעולת חיבור אחת. ספירת הביטים של כל מספר בנפרד לוקחת O(n log n), כי למספר עד n יש בערך log2 n ספרות בינאריות. שתי השיטות משתמשות ב־O(1) זיכרון מעבר למערך הפלט.

Q: למה ‎bits[i] = bits[i >> 1] + (i & 1)‎ עובד?

i >> 1 הוא i ללא הספרה הבינארית האחרונה שלו, ו- i & 1 היא אותה ספרה שהוסרה. מספר האחדות ב- i הוא מספר האחדות במספר הקצר יותר ועוד הספרה האחרונה. עבור 11, שהוא 1011 , המספר הקצר יותר הוא 5 ( 101 , שתי אחדות) והספרה האחרונה היא 1, ולכן ב-11 יש שלוש אחדות.

Q: האם קיימת נוסחת נסיגה אחרת ב־O(n) לספירת ביטים?

כן. i & (i-1) מאפס את ביט ה־1 הנמוך ביותר של i , ולכן bits[i] = bits[i & (i-1)] + 1 עבור כל i שגדול או שווה ל־1. עבור 12 ( 1100 ), 12 & 11 הוא 8 ( 1000 ), שיש בו 1 אחד, ולכן ב־12 יש שניים. השיטה מהירה כמו כלל ההזזה ומשתמשת באותו מילוי משמאל לימין.

Q: האם אפשר להשתמש בפונקציית popcount מובנית?

ברוב השפות יש פונקציה כזאת, כמו Integer.bitCount ב-Java או __builtin_popcount ב-C וב-C++, וקריאה לה עבור כל מספר נותנת תשובה נכונה. מראיינים בדרך כלל מבקשים את הגרסה בלעדיה, כי מטרת הבעיה היא שימוש חוזר בתשובות שכבר חישבת. נוסחת הנסיגה עובדת גם בשפות שאין בהן פונקציה כזאת.

קלמניפולציית ביטים תכנון דינמי

+10

נתון לך מספר שלם n שהוא 0 או יותר. עבור כל מספר i מ-0 עד n, ספר כמה פעמים מופיעה הספרה 1 כשכותבים את i בבינארי. החזר את הספירות כמערך של n+1 איברים, כאשר האיבר i הוא מספר הפעמים שהספרה 1 מופיעה במספר i.

פונקציה

countBits(n: integer) → integer-array

ninteger: המספר האחרון לספירה, 0 או יותר
מחזירהinteger-array: מערך של n+1 ספירות, כאשר הערך במקום i הוא מספר הביטים שערכם 1 ב־i

אילוצים

0 ≤ n ≤ 2 × 10⁴

דוגמאות

קלט: n = 2
פלט: [0, 1, 1]
הסבר: במערכת בינארית, 0 הוא 0, 1 הוא 1 ו-2 הוא 10. כלומר אין ספרות 1, ואז יש אחת, ואז יש אחת.

קלט: n = 5
פלט: [0, 1, 1, 2, 1, 2]
הסבר: 3 הוא 11 ו-5 הוא 101, שני מופעים של 1 בכל אחד מהם, ואילו 4 הוא 100 עם מופע אחד של 1. יחד עם 0, 1 ו-2 מהדוגמה הראשונה, הספירות עבור 0 עד 5 הן 0, 1, 1, 2, 1, 2.

+15 בדיקות נסתרות בשליחה

שאלת המשך

האם תוכל למלא את המערך כולו בזמן O(n), בלי להשתמש בפונקציה מובנית שסופרת ביטים ובלי לספור כל מספר מההתחלה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

ספירת ה־1 בכל מספר בנפרד עובדת, אבל היא חוזרת על עבודה. 13 הוא 1101 ו־6 הוא 110: הביטים של 13 הם הביטים של 6 עם ספרה אחת נוספת בסוף. אם ממלאים את התשובות בסדר עולה, הספירה שנחוצה עבור i כבר נמצאת במערך, וכל איבר דורש חיבור אחד.

ספור את הביטים של כל מספר

האינטואיציה

קח כל מספר מ־0 עד n וספור ישירות את סיביות ה־1 שלו. הסיבית הנמוכה ביותר של x היא x & 1. הוסף אותה למונה, ואז הזז את x ימינה באמצעות x >> 1 כדי שהסיבית הבאה תהיה הנמוכה ביותר. עצור כאשר x מגיע ל־0.

עבור 13, שהוא 1101, הסיביות מתקבלות מימין לשמאל כך: 1, 0, 1, 1, ולכן הספירה היא 3. כל מספר דורש צעד אחד לכל ספרה בינארית, ולמספר עד n יש בערך log2 n ספרות.

לכן זמן הריצה הכולל הוא O(n log n). עבור n = 2 × 10^4 מדובר בכ־20,000 × 15 = 300,000 צעדים, וזה רץ בזמן. אבל עדיין יש כאן עבודה מיותרת: ספירת 13 חוזרת על כל צעד שכבר ביצעת עבור 6. המקום הוא O(1), מלבד מערך הפלט.

אלגוריתם

התחל רשימת תוצאות ריקה.
עבור כל i מ־0 עד n, הגדר את count ל־0 ואת x ל־i.
כל עוד x גדול מ־0, הוסף את x & 1 ל־count והזז את x ימינה בביט אחד.
הוסף את count לתוצאות.
החזר את התוצאות.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

בנה על מחצית המספר

האינטואיציה

הזזה של i ימינה באחד מסירה את הספרה הבינארית האחרונה שלו. לכן ל־i יש בדיוק את ביטי ה־1 של i >> 1, ועוד אחד כאשר הספרה האחרונה שלו היא 1. הספרה האחרונה הזו היא i & 1, ולכן מתקבל הכלל bits[i] = bits[i >> 1] + (i & 1).

עבור כל i שגדול או שווה ל־1, הערך i >> 1 קטן מ־i. אם ממלאים את המערך משמאל לימין, החל מ־bits[0] = 0, האיבר שאליו ניגשים כבר תמיד מלא. זוהי תכנות דינמי: כל תשובה נבנית מתוך תשובה קטנה יותר.

עבור n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. כל איבר דורש הזזה אחת, פעולת AND אחת וחיבור אחד, ולכן זמן הריצה הוא O(n), ואין צורך בזיכרון נוסף מעבר לפלט.

אלגוריתם

צרו מערך bits של n+1 אפסים. bits[0] נשאר 0.
עבור i מ-1 עד n, הגדירו את bits[i] בתור bits[i >> 1] + (i & 1).
החזירו את bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

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

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

במערך יש n+1 איברים, לא n. עבור n = 0 התשובה היא [0]: איבר אחד, עבור המספר 0.
קדימות אופרטורים. ב-Python, ב-C, ב-Java וב-JavaScript, + קודם ל-&, לכן bits[i >> 1] + i & 1 נקרא כך: (bits[i >> 1] + i) & 1. השאר את הסוגריים סביב (i & 1).
חיפוש של bits[i-1] במקום bits[i >> 1]. למספרים שכנים אין כלל פשוט משותף: 7 הוא 111 עם שלושה 1-ים, ו-8 הוא 1000 עם אחד.
ב-Lua וב-R המערכים מתחילים ב-1, לכן הספירה עבור i נמצאת באינדקס i+1, והחיפוש של i >> 1 הוא באינדקס floor(i/2) + 1. ל-Lua של סביבת ההרצה אין אופרטור הזזה, לכן מחלקים לשניים באמצעות math.floor(i / 2).
המרת כל מספר למחרוזת בינארית וספירת התווים 1 נותנת את התשובה הנכונה, אבל יוצרת מחרוזת חדשה עבור כל מספר.

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

מהי סיבוכיות הזמן של ספירת ביטים?

הפתרון הטוב ביותר פועל בזמן O(n): כל אחת מ־n+1 הכניסות נוצרת מכניסה קודמת אחת באמצעות פעולת חיבור אחת. ספירת הביטים של כל מספר בנפרד לוקחת O(n log n), כי למספר עד n יש בערך log2 n ספרות בינאריות. שתי השיטות משתמשות ב־O(1) זיכרון מעבר למערך הפלט.

למה ‎bits[i] = bits[i >> 1] + (i & 1)‎ עובד?

i >> 1 הוא i ללא הספרה הבינארית האחרונה שלו, ו-i & 1 היא אותה ספרה שהוסרה. מספר האחדות ב-i הוא מספר האחדות במספר הקצר יותר ועוד הספרה האחרונה. עבור 11, שהוא 1011, המספר הקצר יותר הוא 5 (101, שתי אחדות) והספרה האחרונה היא 1, ולכן ב-11 יש שלוש אחדות.

האם קיימת נוסחת נסיגה אחרת ב־O(n) לספירת ביטים?

כן. i & (i-1) מאפס את ביט ה־1 הנמוך ביותר של i, ולכן bits[i] = bits[i & (i-1)] + 1 עבור כל i שגדול או שווה ל־1. עבור 12 (1100), 12 & 11 הוא 8 (1000), שיש בו 1 אחד, ולכן ב־12 יש שניים. השיטה מהירה כמו כלל ההזזה ומשתמשת באותו מילוי משמאל לימין.

האם אפשר להשתמש בפונקציית popcount מובנית?

ברוב השפות יש פונקציה כזאת, כמו Integer.bitCount ב-Java או __builtin_popcount ב-C וב-C++, וקריאה לה עבור כל מספר נותנת תשובה נכונה. מראיינים בדרך כלל מבקשים את הגרסה בלעדיה, כי מטרת הבעיה היא שימוש חוזר בתשובות שכבר חישבת. נוסחת הנסיגה עובדת גם בשפות שאין בהן פונקציה כזאת.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

קלט

n = 2

צפוי

[0, 1, 1]