OR XOR AND SHIFT

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

כשרק התחלתי לפתור את השאלות האלה שמתי לב שאני כל הזמן פותרת אותן בדרכים “רגילות” ורק אחר כך מנסה לתרגם אותם לפעולות לוגיות, עד שפתאום זה הכה בי, שאלות bit manipulation זה כמו לשחק “כן לא שחור לבן” עם פעולות לוגיות!

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

אז הרי לפניכן, הגרסה שלי ל-“OR XOR AND SHIFT”.

שאלה 1

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

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

אני אכתוב את האלגוריתם הזה – 

def find_single_number(arr):
	result = arr[0]
	for n in arr[1:]:
		result = result ^ n
	return result

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

שאלה 2

בהינתן 2 מספרים – x,y המשימה היא לבדוק האם הביט במקום ה-y דלוק בייצוג הבינארי של x.
דוגמא – 

x = 300 y = 7 xb = 100101100 bit_set(x,y) = False

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

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

לדוגמא – 

x = 300 y = 7 xb = 100101100 mask = 001000000

כשאני אעשה פעולת AND בין x_b לבין המסיכה שלי, כל הביטים יתאפסו (כולל זה במקום ה-7, כי הביט ה-7 ב-x הוא 0) –

xb & mask = 000000000 = 0

אם הייתי בוחרת ב-x שהביט במקום השביעי שלו שונה מאפס הייתי מקבלת תוצאה שונה מאפס.
לדוגמא – 

x = 330
 y = 7
 xb = 101001010
 mask = 001000000

xb & mask = 001000000 != 0

אז כדי לדעת אם הביט במקום השביעי דלוק, אני צריכה רק לעשות AND עם המסיכה ולבדוק האם התוצאה שונה מאפס.

עכשיו, איך אני יוצרת את המסיכה?

הדרך ה”ביטית” הקלאסית, היא להתחיל ממספר עם ביט דלוק יחיד, ולהזיז אותו שמאלה y-1 מקומות בעזרת פעולת SHIFT, כך שיתקבל ביט דלוק יחיד במקום ה-y.
לדוגמא – 

y = 7
 mask = 1 
 mask = mask << 6
 mask = 1000000

טוב, נראה שיש לי תוכנית, אני אכתוב את האלגוריתם שלי.

def bit_set(x,y):
	mask = 1 << (y-1)
	return (x & mask) != 0

אני אריץ בדיקה –

x = 15
 y = 3
 bit_set(15, 3):
     mask = 100
     1111 & 100 = 100 != 0 → return True

זו הייתה שאלה ממש מגניבה, הידד!

שאלה 3

בהינתן 3 מספרים – x,y,z המשימה היא לבדוק האם הביטים במקום ה-x ובמקום ה-y הם הביטים היחידים שדלוקים בייצוג הבינארי של z.

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

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

לדוגמא – 

x = 5
 y = 10

המספר הבינארי שהביטים ה-5 וה-10 שלו דלוקים וכל השאר כבויים הוא – 

Nb = 1000010000 → N = 528

אז במקום להשתמש במסיכות על Z, אני יכולה ליצור את המספר הבינארי הרצוי ולהשוות את הערך הדצימלי שלו ל-Z.
איך אני יוצרת את המספר שהביטים במקום ה-5 וה-10 שלו דלוקים? 
אני יודעת איך ליצור מספר שכולו מאופס מלבד ביט אחד (ככה יצרתי את המסיכה בשאלה הקודמת).
אם יהיו לי שני מספרים מאופסים לחלוטין עם ביט דלוק יחיד – אחד עם ביט דלוק במקום ה-x ואחד עם ביט דלוק במקום ה-y, אני אוכל לעשות ביניהם פעולת OR ולקבל מספר עם שני ביטים דלוקים.

לדוגמא –

n1 = 1 << 9 = 1000000000
 n2 = 1 << 4 = 10000
 N = n1 | n2 = 1000010000

אני אכתוב את האלגוריתם – 

def exact_bit_set(x,y, z):
	n1 = 1 << (x-1)
	n2 = 1 << (y-1)
	N = n1 | n2
	return z == N

אני אריץ בדיקה – 

x = 2 y = 8 z = 20
 exact_bit_set(2, 8, 20):
 n1 = 10
 n2 = 10000000
 N = 10000010 → N = 130 != 20
 return False

ווהו, התגברתי גם על השאלה הזו!

שאלה 4

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

x = 7
 get_all_powers_of_two(x) = [1, 2, 4]
 x = 330
 get_all_powers_of_two(x) = [2, 8, 64, 256]

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

לדוגמא – 

X = 7
Xb = 111 = 1(2^2) + 1(2^1) + 1*(2^0) = 4 + 2 + 1 = 7X = 7
X = 330
Xb = 101001010 = 1(2^8) + 0(2^7) + 1(2^6) + 0(2^5) + 0(2^4) + 1(2^3) + 0(2^2) + 1(2^1) + 0*(2^0) = 256 + 64 + 8 + 2 = 330

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

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

אני אכתוב את האלגוריתם הזה –

def get_all_powers_of_two(x):
	res = []
	power_of_two = 1
	while power_of_two <= x:
		if power_of_two & x != 0:
			res.append(power_of_two)
		power_of_two = power_of_two << 1
	return res

מגניב, אני אריץ בדיקה – 

X = 330
 get_all_powers_of_two(330):
     res = []
     power_of_two = 1
     1 AND 101001010 = 0
     power_of_two = 2
     10 AND 101001010 = 1
     res = [2]
     power_of_two = 4
     100 AND 101001010 = 0
     power_of_two = 8
     1000 AND 101001010 = 1
     res = [2,8]
     power_of_two = 16
     10000 AND 101001010 = 0
     power_of_two = 32
     100000 AND 101001010 = 0
     power_of_two = 64
     1000000 AND 101001010 = 1
     res = [2,8,64]
     power_of_two = 128
     10000000 AND 101001010 = 0
     power_of_two = 256
     100000000 AND 101001010 = 1
     res = [2,8,64, 256]
     power_of_two = 512
     1000000000 AND 101001010 = 0
     return [2,8,64, 256]

וואו, אני חייבת להודות שזה ממש יפה 🙂
מה הסיבוכיות של האלגוריתם הזה?
יש כאן לולאה שבכל פעולה מכפילה את power_of_two ב-2 ובודקת אם הוא גדול מ-x. הלולאה תתבצע כמספר הפעמים שצריך להכפיל את power_of_two ב-2 לפני שהוא עובר את הגודל של x – כלומר log₂x פעמים. הסיבוכיות של האלגוריתם היא (O(logx.

שאלה 5

נתון מספר מסוג  unsigned int. המשימה היא להחזיר את המספר שהוא היפוך הביטים של המספר המקורי.
לדוגמא – 

x = 3
 xb = 00000000000000000000000000000011
 reverse_bits(x) = 11000000000000000000000000000000

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

x = 1
xb = 00000000000000000000000000000001
reverse_bits(x) = 10000000000000000000000000000000
x = 0
reverse_bits(x) = 0
x = 65536
xb = 00000000000000010000000000000000
reverse_bits(x) = 00000000000000100000000000000000

אני רוצה ליצור מספר חדש שמכיל את כל הביטים של x מהסוף להתחלה.
32 ביטים זה קצת הרבה לעכל, איך הייתי עושה את זה אם הייתי צריכה להפוך רק 4 ביטים?

נגיד – 

x = 5
xb = 0101
revers_3_bits(x) = 1010

אני אתחיל מהביט הראשון (הימני ביותר) ב-x שצריך להיות הביט השמאלי ביותר בתוצאה.
איך אני מבודדת את הביט הראשון? עם מסיכה – 

mask = 1
first_bit = x & mask = 1

ואיך אני מזיזה אותו למקום השמאלי ביותר? עם SHIFT – 

left_result_bit = first_bit << 3 = 1000

עכשיו את ביט השני – 

mask = 1 << 1 = 10
second_bit = x & mask = 0
second_left_result_bit = second_bit << 1 = 0

עכשיו את ביט השלישי – 

mask = 1 <> 1 = 10

והביט הרביעי – 

mask = 1 <> 1 = 0

התוצאה הסופית תהיה פעולת OR על כל תוצאות הביניים, כדי לאחד את הביטים בכל המקומות השונים למספר אחד.

result = 
 left_result_bit | second_left_result_bit | third_left_result_bit | fourth_left_result_bit = 
 1000 | 0 | 10 | 0 = 1010

מה בעצם עשיתי פה?

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

אחר כך עשיתי פעולת OR על כל הביטים של התוצאה כדי לקבל את התוצאה השלמה.

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

אם במקום להשתמש במסיכה על המיקום המדויק של הביט הייתי תמיד מזיזה את הביט שאני ממוקדת עליו לקצה, אז הייתי יודעת בדיוק כמה מקומות ימינה אני צריכה להזיז את התוצאה (ותמיד הייתי צריכה להזיז אותה ימינה).
כך – 

x = 5
xb = 0101
mask = 1
first_bit = x & mask = 1
left_result_bit = first_bit <> 1 & mask = 010 & 1 = 0
second_left_result_bit = second_bit <> 2 & mask = 01 & 1 = 1
third_left_result_bit = third_bit <>3 & mask = 0 & 1 = 0
fourth_left_result_bit = third_bit << 1 = 0
result = 1000 | 0 | 10 | 0 = 1010

אוקי, זה כבר נראה הרבה יותר טוב.
אני אכתוב את האלגוריתם – 

[sourcecode language="python" wraplines="false" collapse="false"]
def revers_bits(x):
	result = 0
	for i in range(0,32):
		current_bit = x >> i & 1
		result = result | current_bit << (32 - i - 1)
	return result

אני אריץ בדיקה – 

x = 18
xb = 10010
revers_bits(x):
     result = 0
     i = 0
     current_bit = 1001 & 1 = 1
     result = 0 | 1 << 31 = 1000…000
     i = 1
     current_bit = 100 & 1 = 0
     result = 1
     i = 2
     current_bit = 10 & 1 = 0
     result = 1
     i = 3
     current_bit = 1 & 1 = 1
     result = 1000…000 | 1 << 28 = 1001000…000
     …..
     return 10010000000000000000000000000000

ווהו!

טוב, נראה לי שזה מספיק ביטים להיום, אבל זה היה הרבה יותר נחמד (ומאתגר) ממה שציפיתי.

את הקוד לכל השאלות אפשר למצוא בתיקייה בגיט – https://github.com/mgershovitz/maya_solves/tree/master/bit_manipulation