השבוע הנושא של bit manipulation עלה באחת מקבוצות הפייסבוק שאני חברה בהן כנושא שיכול להיות מבלבל ומאתגר בראיונות. הרעיון בדרך כלל בשאלות ביטים הוא לפתור משימה שהייתה יכולה להיות סופר פשוטה באמצעים רגילים, בלי להשתמש בפעולות מתמטיות, מחרוזות או כל אמצעי נוח אחר.
כשרק התחלתי לפתור את השאלות האלה שמתי לב שאני כל הזמן פותרת אותן בדרכים "רגילות" ורק אחר כך מנסה לתרגם אותם לפעולות לוגיות, עד שפתאום זה הכה בי, שאלות bit manipulation זה כמו לשחק "כן לא שחור לבן" עם פעולות לוגיות!
ברגע שהתחלתי להתייחס לשאלות האלה כמו משחקים, נהיה לי קל יותר לחפש את הזוית הביטית במקום להיות מיואשת מכך שאני לא יכולה פשוט לקודד כמו שאני רגילה.
אז הרי לפניכן, הגרסה שלי ל-"OR XOR AND SHIFT".
נתונה רשימה של מספרים מסוג unsigned int, כאשר כל המספרים ברשימה מלבד אחד מופיעים בדיוק פעמיים, ואחד מופיע פעם אחת בלבד.
המשימה היא למצוא את המספר הבודד בסיבוכיות לינארית וללא שימוש בזיכרון נוסף.
ברגע שאני רואה שאלה מהסוג הזו שמדבר על זוגות של מספרים זהים אני ישר חושבת על פעולת XOR.
הפעולה XOR היא פעולה לוגית שמבטלת את ההשפעה של ביטים זהים ומשאירה רק את ההשפעה של ביטים שונים.
לכן, אם אני אעשה פעולת XOR בין כל המספרים ברשימה, כל המספרים שמופיעים בזוגות יבטלו זה את זה, ורק המספר הבודד ישאר.
הסיבוכיות של המעבר על המערך היא לינארית. לסיבוכיות של פעולת ה-XOR, למרות שהיא תלויה במספר הביטים בייצוג הבינארי אני אתייחס כאן כ-(O(1, כפי שהייתי מתייחסת לכל פעולה חשבונית אחרת, אלא אם כן יבקשו ממני במיוחד להתייחס לסיבוכיות הפנימית של XOR לוגי.
לכן הסיבוכיות של האלגוריתם היא (O(N.
בהינתן 2 מספרים – x,y המשימה היא לבדוק האם הביט במקום ה-y דלוק בייצוג הבינארי של x.
מגניב, שאלה קצת יותר מורכבת שדורשת להשתמש בוודו הקסום של מסיכות :).
אז הרעיון של מסיכות יכול להיות קצת מפחיד בהתחלה אם לא רגילים אליו, אבל ברגע שנופל האסימון זה ממש ברור.
לדוגמא – במקרה של השאלה הזו אני רואה שכל מה שחשוב לי הוא הערך של הביט ה-7 בייצוג הבינארי של x, ואני רוצה להתעלם מכל דבר אחר ורק לבדוק את הערך שלו.
איך אני עושה את זה?
אני רוצה להשתמש במסיכה שתהיה אדישה לערך של כל הביטים מלבד הביט במקום ה-7. הפעולה המתאימה כאן היא פעולת AND.
פעולת AND בין כל הביטים שלא מעניינים אותי ו-0 יאפס אותם, ופעולת AND בין הביט שמעניין אותי ו-1 יבדוק את הערך שלו – אם הוא 0 התוצאה תתאפס, ואם הוא 1 התוצאה תהיה 1.
אם הייתי בוחרת ב-x שהביט במקום השביעי שלו שונה מאפס הייתי מקבלת תוצאה שונה מאפס.
אז כדי לדעת אם הביט במקום השביעי דלוק, אני צריכה רק לעשות AND עם המסיכה ולבדוק האם התוצאה שונה מאפס.
עכשיו, איך אני יוצרת את המסיכה?
הדרך ה"ביטית" הקלאסית, היא להתחיל ממספר עם ביט דלוק יחיד, ולהזיז אותו שמאלה y-1 מקומות בעזרת פעולת SHIFT, כך שיתקבל ביט דלוק יחיד במקום ה-y.
טוב, נראה שיש לי תוכנית, אני אכתוב את האלגוריתם שלי.
זו הייתה שאלה ממש מגניבה, הידד!
בהינתן 3 מספרים – x,y,z המשימה היא לבדוק האם הביטים במקום ה-x ובמקום ה-y הם הביטים היחידים שדלוקים בייצוג הבינארי של z.
השאלה הזו די דומה לשאלה 3 אבל יש לה טוויסט – בניגוד לשאלה הקודמת, פה אני לא רוצה להתעלם מכל הביטים מלבד אחד או שניים, בשאלה הזו כל הביטים חשובים, ואני רוצה לבדוק את הערכים של כולם.
כיוון שמדובר בשאלת ביטים הנטייה האוטומטית שלי היא להשתמש במסיכה, אבל אני חושדת שאפשר לעשות את הבדיקה הזו באופן אפילו יותר פשוט – מספר בינארי שיש לו ביטים דלוקים וכבויים במקומות ידועים הוא פשוט מספר ספציפי.
אז במקום להשתמש במסיכות על Z, אני יכולה ליצור את המספר הבינארי הרצוי ולהשוות את הערך הדצימלי שלו ל-Z.
איך אני יוצרת את המספר שהביטים במקום ה-5 וה-10 שלו דלוקים?
אני יודעת איך ליצור מספר שכולו מאופס מלבד ביט אחד (ככה יצרתי את המסיכה בשאלה הקודמת).
אם יהיו לי שני מספרים מאופסים לחלוטין עם ביט דלוק יחיד – אחד עם ביט דלוק במקום ה-x ואחד עם ביט דלוק במקום ה-y, אני אוכל לעשות ביניהם פעולת OR ולקבל מספר עם שני ביטים דלוקים.
ווהו, התגברתי גם על השאלה הזו!
בהינתן מספר, צריך להחזיר רשימה של חזקות של 2 שהסכום שלהם שווה למספר הנתון.
קול, שאלה מעניינת.
ברגע שראיתי שזו שאלה ביטית, הכיוון של התשובה כבר נראה ברור לגמרי. הייצוג הבינארי של מספר הוא בדיוק זה – הייצוג של כל החזקות של 2 שמרכיבות את המספר.
באופן תיאורטי יכולתי לעבור על כל הביטים של המספר ועבור כל ביט דלוק לקחת את החזקה המתאימה של 2, אבל זה ידרוש ממני להשתמש בפעולות מתמטיות. מה תהיה הדרך הביטית הטהורה לפתור את זה?
אני יכולה ליצור סדרה של מסכות עם ביט אחד דלוק, שמייצגות חזקות של 2 (מספר שיש לו רק ביט אחד דלוק הוא בדיוק חזקה של 2), ולעשות פעולת AND בין המסיכה למספר כדי לבדוק אם החזקה הזו קיימת במספר.
מה הסיבוכיות של האלגוריתם הזה?
יש כאן לולאה שבכל פעולה מכפילה את power_of_two ב-2 ובודקת אם הוא גדול מ-x. הלולאה תתבצע כמספר הפעמים שצריך להכפיל את power_of_two ב-2 לפני שהוא עובר את הגודל של x – כלומר log2x פעמים. הסיבוכיות של האלגוריתם היא (O(logx.
נתון מספר מסוג unsigned int. המשימה היא להחזיר את המספר שהוא היפוך הביטים של המספר המקורי.
האמת היא שזו שאלה שאין לי כל כך מושג איך לגשת אליה, אז אני אתחיל מלבחון כמה דוגמאות קטנות ומה צריך לקרות בהן.
אני רוצה ליצור מספר חדש שמכיל את כל הביטים של x מהסוף להתחלה.
32 ביטים זה קצת הרבה לעכל, איך הייתי עושה את זה אם הייתי צריכה להפוך רק 4 ביטים?
אני אתחיל מהביט הראשון (הימני ביותר) ב-x שצריך להיות הביט השמאלי ביותר בתוצאה.
התוצאה הסופית תהיה פעולת OR על כל תוצאות הביניים, כדי לאחד את הביטים בכל המקומות השונים למספר אחד.
מה בעצם עשיתי פה?
כל פעם בודדתי ביט יחיד בעזרת מסיכה על המיקום שלו, וכדי להביא את הביט למקום המתאים בתוצאה הזזתי אותו ימינה או שמאלה בהתאם למיקום שלו מהמרכז.
אחר כך עשיתי פעולת OR על כל הביטים של התוצאה כדי לקבל את התוצאה השלמה.
זה עובד, אבל אני לא כל כך אוהבת את זה שלפעמים אני צריכה לזוז שמאלה ולפעמים ימינה, האם יש דרך קצת יותר אלגנטית לעשות את זה?
אם במקום להשתמש במסיכה על המיקום המדויק של הביט הייתי תמיד מזיזה את הביט שאני ממוקדת עליו לקצה, אז הייתי יודעת בדיוק כמה מקומות ימינה אני צריכה להזיז את התוצאה (ותמיד הייתי צריכה להזיז אותה ימינה).
אוקי, זה כבר נראה הרבה יותר טוב.
טוב, נראה לי שזה מספיק ביטים להיום, אבל זה היה הרבה יותר נחמד (ומאתגר) ממה שציפיתי.