Number of 1 Bits

Q: מהי סיבוכיות הזמן של Number of 1 Bits?

לולאת ההזזה מתבצעת פעם אחת לכל ספרה בינארית: O(log n) , לכל היותר 31 צעדים כאן. הלולאה n & (n-1) מתבצעת פעם אחת לכל ביט שערכו 1: O(k) , כאשר k היא התשובה. שתיהן משתמשות בזיכרון נוסף של O(1) .

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

+10

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

פונקציה

hammingWeight(n: integer) → integer

ninteger: מספר שלם אי-שלילי שמתאים למספר שלם signed בן 32 סיביות
מחזירהinteger: מספר הספרות 1 בייצוג הבינארי של n

אילוצים

0 ≤ n ≤ 2³¹-1

דוגמאות

קלט: n = 11
פלט: 3
הסבר: 11 הוא 1011 בבינארי, שהם 8 + 2 + 1. שלוש מתוך ארבע הספרות הבינאריות שלו הן 1, ולכן התשובה היא 3.

קלט: n = 128
פלט: 1
הסבר: 128 הוא 2^7, נכתב 10000000: 1 יחיד ואחריו אפסים, ולכן התשובה היא 1.

שאלת המשך

אם הפונקציה הזאת תרוץ מיליוני פעמים, איך אפשר לספור את הביטים של מספר בן 32 סיביות באמצעות ארבע חיפושים בטבלה של 256 ספירות שחושבו מראש?

רמזים

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

נפתחו 0 מתוך 3

פתרון

עבור על הספרות הבינאריות של n בלי לבנות מחרוזת. קריאת הסיבית האחרונה והזזתה הצידה דורשת צעד אחד לכל ספרה בינארית, עד 31. ניקוי סיבית ה־1 הנמוכה ביותר באמצעות n & (n-1) דורש צעד אחד לכל סיבית 1, בדיוק כמספר הסיביות בתשובה.

בדקו את הביט האחרון והזיזו ימינה

האינטואיציה

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

הלולאה נעצרת כאשר n הוא 0, ולכן היא לעולם אינה עוברת על אפסים מובילים: בערך log2(n) צעדים, 8 עבור 128 ולכל היותר 31. היא מאחסנת רק את n ואת הספירה.

אלגוריתם

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

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

נקה את הסיבית הנמוכה ביותר באמצעות n & (n-1)

האינטואיציה

הפחתת 1 הופכת את הביט 1 הנמוך ביותר ל־0 ואת כל הביטים 0 שמתחתיו ל־1, ומשאירה את הביטים שמעליו ללא שינוי. לכן n & (n-1) משאירה את הביטים העליונים ומאפסת את הביט 1 הנמוך ביותר: 12 הוא 1100, 11 הוא 1011, ו־1100 & 1011 הוא 1000.

כל צעד מסיר בדיוק ביט 1 אחד, ולכן מספר הצעדים עד ש־n הוא 0 הוא התשובה. 128 דורש צעד אחד במקום 8, אם כי 2^31-1 עדיין דורש 31. ל־Lua 5.1 אין אופרטורים לביטים, ולכן הגרסה שלה מוצאת את ביט 1 הנמוך ביותר באמצעות חלוקה חוזרת ב־2 ומחסרת אותו; הלולאה עדיין רצה פעם אחת לכל ביט 1.

אלגוריתם

התחל מונה ב־0.
כל עוד n אינו 0, החלף את n ב־n & (n-1).
הוסף 1 למונה אחרי כל החלפה.
החזר את המונה.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

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

ביצוע לולאה כל עוד n > 1. הלולאה נעצרת לפני הביט האחרון שערכו 1 ומחזירה 0 עבור n = 1.
חלוקה שמחזירה מספר עשרוני. ב-JavaScript, ב-Lua וב-R, התוצאה של 11 / 2 היא 5.5, והשאריות שמתקבלות בהמשך הן שברים. עגל כלפי מטה באמצעות Math.floor, math.floor או %/%, או השתמש בהזזה במקום.
כתיבת n & 1 ב-Lua 5.1. אין בה אופרטורים לעבודה עם ביטים, ולכן הקוד לא מתקמפל; השתמש ב-n % 2 וב-math.floor(n / 2).

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

מהי סיבוכיות הזמן של Number of 1 Bits?

לולאת ההזזה מתבצעת פעם אחת לכל ספרה בינארית: O(log n), לכל היותר 31 צעדים כאן. הלולאה n & (n-1) מתבצעת פעם אחת לכל ביט שערכו 1: O(k), כאשר k היא התשובה. שתיהן משתמשות בזיכרון נוסף של O(1).

האם קיימת פונקציה מובנית שסופרת ביטים שהוגדרו?

ברוב השפות יש פונקציה כזאת, שלעתים קרובות ממומשת באמצעות הוראת מעבד יחידה: Integer.bitCount ב-Java, __builtin_popcount ב-GCC, bits.OnesCount ב-Go, count_ones ב-Rust ו-int.bit_count ב-Python 3.10 ואילך. בריאיון, כתוב את הלולאה והזכר את הפונקציה המובנית.

מה ההבדל בין משקל המינג למרחק המינג?

משקל המינג של מספר הוא מספר הספרות הבינאריות שלו שהן 1, וזה מה שהבעיה הזו מחזירה. מרחק המינג בין שני מספרים הוא מספר מיקומי הביטים שבהם הם שונים: יש לספור את הביטים שערכם 1 בתוך a ^ b, מכיוון ש-XOR קובע את הערך 1 בדיוק במיקומים שבהם הם שונים.

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

n = 11

הפלט הצפוי