אתגר תכנותי: היפוך ביטים של מספר בינארי באמצעות אופרציות Bitwise

באתגר זה, תכתוב פונקציה המבצעת את הפעולות הבאות:

1. מקבלת מספר בינארי ומספר ביטים.
2. הופכת את סדר הביטים של המספר הבינארי.
3. מחזירה את הייצוג העשרוני של המספר הבינארי לאחר ההיפוך. עליך לבצע את המשימה באמצעות שימוש באופרציות bitwise בלבד.

דוגמה

קלט:

• מספר בינארי: 0101
• מספר ביטים: 4

פלט:

• 10

הסבר:
המספר הבינארי 0101 (הייצוג הבינארי של 5 ב-4 ביטים) הופך ל-1010. הייצוג העשרוני של 1010 הוא 10.

פתרון מוצע

def reverse_bits(n, num_bits=8):
    reversed_result = 0  # אתחול התוצאה המהופכת
    for i in range(num_bits):  # עיבוד כל הביטים
        right_shifted = n >> i  # הזזה לימין כדי להגיע לביט ה-i
        current_bit = right_shifted & 1  # חילוץ הביט הפחות משמעותי
        left_shift_amount = num_bits - 1 - i  # חישוב העמדה החדשה (הפוכה)
        current_result = current_bit << left_shift_amount  # יצירת הביט בעמדה החדשה
        reversed_result |= current_result  # הוספת הביט לתוצאה הסופית
    return reversed_result

נסביר:

הפונקציה מחזירה את המספר הבינארי לאחר היפוך הביטים, באמצעות הצעדים הבאים:

1. לולאה על הביטים במספר:

   • הלולאה רצה כמספר הביטים (לדוגמה, אם יש 4 ביטים – הלולאה רצה 4 פעמים).

2. חילוץ הביט הנוכחי (LSB):

   right_shifted = n >> i  
   current_bit = right_shifted & 1
   

   • הזזת הביטים ימינה מסירה ביטים משמאל.
   • פעולת AND עם 1 מבודדת את הביט השמאלי ביותר.

3. חישוב המיקום החדש:

   left_shift_amount = num_bits - 1 - i
   

   • חישוב המיקום החדש שבו הביט ההופכי יימצא.

4. הזזת הביט לעמדה החדשה:

   current_result = current_bit << left_shift_amount
   

   • הזזת הביט לעמדה החדשה באמצעות הזזה לשמאל עד לעמדה החדשה.

5. עדכון התוצאה המהופכת:

   reversed_result |= current_result
   

   • הפעלת אופרציית OR בין הביט שהוזז למיקום הרצוי לבין התוצאה הנצברת.

6. החזרת התוצאה הסופית:

   return reversed_result

   • לאחר שהלולאה מסיימת לרוץ, הפונקציה מחזירה את התוצאה הסופית אותה צברה הלולאה.

נבדוק:

# Test cases
test_cases = [
    [0b0101, 4, 10],
    [0b0000, 4, 0],
    [0b1111, 4, 15],
    [0b1010, 4, 5],
    [0b11100010100111001101111010010101, 32, 2843425095],
]

# Print Header
print(f"{'Result'.ljust(13)}{'Expected'.ljust(13)}{'Conclusion'}")
print(f"{'-'*13}{'-'*13}{'-'*10}")

# Loop through test cases and print results in table format
for b, num_bits, expected in test_cases:
    res = reverse_bits(b, num_bits)
    conclusion = "😄" if res == expected else "😭"
    print(f"{str(res).ljust(13)}{str(expected).ljust(13)}{conclusion}")

print("Finito Programa")

סיבוכיות

1. זמן ריצה: O(num_bits) – הפונקציה רצה פרופורציונלית למספר הביטים.
2. שימוש בזיכרון: O(num_bits) – נדרש אחסון תוצאה זמנית באורך מספר הביטים.

לסיכום

הפתרון משתמש באופרציות bitwise בלבד כדי לבצע את היפוך הביטים באופן יעיל ומדויק. אתגר תכנותי זה ממחיש את הגמישות של הפעלת אופרציות על ביטים.

אולי גם זה יעניין אותך?

עבודה עם מספרים בינאריים ואופרציות Bitwise בפייתון

אתגר תכנותי: מציאת מספר הביטים שהם 1 במספר בינארי

מהם מספרים בינאריים וכיצד להמיר מספרים מייצוג עשרוני לבינארי והפוך

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים