בינארי במיון תקשוב - מדריך מלא ממיר ראשון ועד יום המבחן

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

למה בכלל בינארי?

מחשב בנוי פיזית ממיליוני טרנזיסטורים שכל אחד מהם מופעל או כבוי. אין מצב ביניים. לכן שיטת הספירה הטבעית ביותר למחשב היא כזו שמשתמשת בשני סימנים בלבד - 0 ו-1. בעוד שאנשים סופרים בעשרוני (עשרה סימנים), המחשב סופר בבסיס בינארי. כל מה שעושים בעשרוני אפשר לעשות בבינארי - רק עם פחות סימנים ויותר ספרות.

המרה בינארי לעשרוני

כל ספרה בינארית מייצגת חזקה של 2, מימין לשמאל: 1, 2, 4, 8, 16, 32, 64, 128. כדי להמיר, סוכמים את החזקות שבמיקומיהן מופיע 1.

10101010 בינארי = 128 + 32 + 8 + 2 = 170 עשרוני. שינון שמונה החזקות הראשונות של 2 הוא תנאי הכרחי, וזו כנראה ההשקעה עם ההחזר הגבוה ביותר בכל הנושא: כמה דקות שינון בערב אחד חוסכות חישוב חוזר בכל שאלה בהמשך. שווה לשנן אותן בשני הכיוונים, כלומר גם 64 שווה 2 בחזקת 6 וגם 2 בחזקת 6 שווה 64, כי חלק מהשאלות מנוסחות דרך מספר הביטים ולא דרך הערך.

המרה עשרוני לבינארי - שתי שיטות

שיטת חלוקה ב-2: מחלקים את המספר העשרוני שוב ושוב ב-2, רושמים את השארית. הקוד הבינארי הוא השאריות מלמטה למעלה. דוגמה: 53. 53/2=26 שארית 1. 26/2=13 שארית 0. 13/2=6 שארית 1. 6/2=3 שארית 0. 3/2=1 שארית 1. 1/2=0 שארית 1. מלמטה: 110101.

שיטת חיסור החזקות: מורידים את החזקה הגדולה ביותר של 2 שעדיין נכנסת. דוגמה: 53 → 32 נכנסת (1 במקום 32). 53-32 = 21 → 16 נכנסת (1 במקום 16). 21-16=5 → 4 נכנסת (1 במקום 4). 5-4=1 → 1 נכנסת (1 במקום 1). מספרים: 1 1 0 1 0 1 = 110101.

חיבור בבינארי

חיבור בבינארי עובד כמו חיבור עשרוני - רק שכאן הנשיאה מתרחשת ב-2 ולא ב-10. הכללים: 0+0=0. 0+1=1. 1+0=1. 1+1=10 (כלומר 0 עם נשיאת 1). 1+1+1=11 (כלומר 1 עם נשיאת 1). דוגמה: 1011 + 0110 = 10001.

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

מספרים שליליים - שלילה דו-משלימה

כיצד המחשב מייצג מספר שלילי? באמצעות "שלילה דו-משלימה" (Two's Complement). הכלל: כדי לקבל את ה-X-, הופכים את כל הביטים של X (0 ל-1 ו-1 ל-0), ואז מוסיפים 1. דוגמה: 5 ב-8 ביטים = 00000101. הופכים: 11111010. מוסיפים 1: 11111011 = -5.

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

טריקים שמקצרים זמן פתרון

כפל ב-2: זהה להוספת 0 בסוף. 101 (5) × 2 = 1010 (10). תקראו לזה Shift Left.

חלוקה ב-2: זהה למחיקת הספרה הימנית. 1010 (10) ÷ 2 = 101 (5). תקראו לזה Shift Right.

בדיקת זוגיות: מספר זוגי תמיד מסתיים ב-0 בבינארי. מספר אי-זוגי - ב-1. זאת בדיקה מיידית.

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

מה באמת מופיע בשאלות - מבט על מאגר התרגול שלנו

מאגר הבינארי באתר מכיל 90 שאלות בשלוש רמות קושי. כשעברנו עליהן וסיווגנו לפי סוג, התמונה היתה ברורה: הקבוצה הגדולה ביותר, כשליש מהשאלות, היא המרות פשוטות בשני הכיוונים, כולל המרה להקסדצימלי. אחריה, כחמישית, פעולות חשבון בינאריות. הקבוצה השלישית היא שאלות שערים לוגיים, ורק מיעוט קטן עוסק ישירות במשלים ל-2.

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

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

תוכנית תרגול קצרה שעובדת

התרגול היומי שאנחנו ממליצים עליו לוקח פחות מרבע שעה: עשר המרות בשני הכיוונים, חמש פעולות חשבון בינאריות, ושלוש שאלות על הייצוג עצמו. אחת לכמה ימים הוסיפו שתי שאלות משלים ל-2, שהן היחידות שדורשות חזרה מרווחת כדי שלא יישכחו.

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