כתיבת קוד — שיעור 1

ארכיטקטורת מחשב: איך מחשב באמת עובד

כל 2 משימות הקוד שנשמרו מהשיעור מופיעות כאן, עם דרישות, דוגמאות וקוד פתיחה. אפשר לכתוב פתרון בעורך המקומי וללחוץ על „בדיקת AI” לקבלת ציון, רמזים והערות.

T1 · מתחיל 100 נק' ~8 דק' algorithmic

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

כל מספר חי בזיכרון כרצף ביטים. נתון מספר שלם אי-שלילי n. החזר את מספר הביטים הדלוקים (1) בייצוגו הבינארי — 'משקל האמינג'. פתרון יעיל אינו סורק את כל 64 הסיביות אלא מדלג ישירות מביט דלוק אחד לבא אחריו.

דוגמאות

count_set_bits(0) → 0

count_set_bits(7) → 3

count_set_bits(8) → 1

פתרון-ייחוס משקל האמינג — ספירת ביטים דלוקים ›

def count_set_bits(n: int) -> int:
    c = 0
    while n:
        n &= n - 1      # מכבה את הביט הדלוק הנמוך ביותר
        c += 1
    return c

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T2 · בסיסי 200 נק' ~20 דק' algorithmic

מחבר בינארי Ripple-Carry (O(n))

בנה את פעולת החיבור של ה-ALU במו ידיך. נתונות שתי מחרוזות בינאריות a ו-b (תווי '0'/'1' בלבד, אורכים שרירותיים ואולי שונים, אפסים מובילים אפשריים). החזר את סכומן כמחרוזת בינארית ללא אפסים מובילים (פרט ל-"0" עצמו). חובה O(n): קלט של מיליון ביטים חייב לרוץ בזמן. בנייה תמימה שמשרשרת תו בראש המחרוזת בכל צעד היא O(n²) ותיפסל ב-timeout.

דוגמאות

add_binary('1','1') → '10'

add_binary('101','11') → '1000'

add_binary('0','0') → '0'

פתרון-ייחוס מחבר בינארי Ripple-Carry (O(n)) ›

def add_binary(a: str, b: str) -> str:
    i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        s = carry
        if i >= 0: s += a[i] == '1'; i -= 1
        if j >= 0: s += b[j] == '1'; j -= 1
        out.append('1' if (s & 1) else '0')
        carry = s >> 1
    out.reverse()                      # append+reverse = O(n) (לא שרשור מלפנים!)
    res = ''.join(out).lstrip('0')
    return res if res else '0' 

הפתרון שלךהפתרון נשמר מקומית אוטומטית.