העתקת ביטים

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

נתונים שני מספרים באורך 32 ביט – M,N ושני אינדקסים – I,J.
המשימה היא לכתוב פונקציה שמעתיקה את M לתוך N בין האינדקסים j ו-i.
אפשר להניח שההפרש בין j ל-i גדול מספיק כדי להכיל את כל M.

לדוגמא – 

N=10000000000 M=10011 j=6 i=2 copy_bits(N,M,i,j) = 10001001100

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

לדוגמא – 

N=10001111100 M=10011 j=6 i=2

במקרה של N כזה, פעולת העתקה צריכה לתת את אותה התוצאה כמו בדוגמא למעלה, אבל פעולת OR תיתן לנו תוצאה לא נכונה.

N | M = 10001111100

המסקנה היא שצריך קודם לאפס את הטווח j-i ב-N, ורק אז לעשות OR בינו לבין M.

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

כדי ליצור את המספר אני אתחיל מ- 1- (רצף של אחדות) – 

x = -1 (x = 1111…..11)

שנית, אני אעשה לו shift שמאלה i פעמים, כדי לקבל i אפסים מימין – 

x = x << i
 (x = 111…1100)

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

אני אקח 1 ואעשה לו shift ימינה j+1 פעמים (כדי לקבל 1 במקום ה-j+2 ו-j+1 אפסים מימינו).

y = 1 << j+1
(y = 000…1000)

עכשיו אני אחסיר מ-y אחד, מה שיהפוך את כל האפסים מימין ל-1 שלי לאחדות.

y = y – 1 (y = 000111…11)

כעת, אני אעשה פעולת AND בין x ו-y כדי לקבל מסיכה הפוכה מזו שאני רוצה (אחדות באמצע, אפסים בצד)

mask = x & y
 (mask = 0001111..11100)

ולבסוף, אני אעשה פעולת NOT למסיכה כדי לקבל את המסיכה הסופית שאני רוצה – 

mask = ~mask (mask = 111000…00011)

מעולה! עכשיו קיבלתי מסיכה עם אחדות משמאל לאינדקס j ומימין לאינדקס i ואפסים ביניהם.

אני אעשה פעולת AND למסיכה הזו עם N כדי לאפס את הטווח שלי – 

N = N & mask
(N= N0N1N2000..00N31N32)

ועכשיו שהטווח מאופס אני יכולה לעשות OR בין N ו-M ו-M יועתק לתוך הטווח ב-N – 

N = N | M
(N = N0N1N2M0M1...Mj-iN31N32)

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

אני אכתוב אותו מהר ואבדוק על כמה דוגמאות.

def copy_bits(N,M,i,j):
	x = -1 << i
	y = (1 << j+1) - 1
	mask = ~(x & y)
	N = N & mask
	return N | M

בעבור הדוגמא למעלה – 

N=10001111100
M=10011
j=6 i=2

copy_bits(10001111100,10011,2,6):
 x = 1111111111….1100
 y = 000000111….1111
 mask = 11111100...00011
 N = 10001111100 & 11111100...00011 = 10000000000
 return 10000000000 | 10011 = 10000010011

אוי לא, הנה טעות.

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

כדי לסדר את זה אני אזיז גם את M שמאלה i ביטים (כדי לקבל i אפסים בצד השמאלי) לפני ההעתקה –

def copy_bits(N,M,i,j):
	x = -1 << i
	y = (1 << j+1) - 1
	mask = ~(x & y)
	N = N & mask
	M = M << i
	return N | M

מה יקרה במקרה שבו N=0?
המסיכה לא תשנה כלום, N יישאר 0, וה-OR יעתיק את M.

מה יקרה במקרה שבו M=0?
הביטים שיועתקו יהיו אפסים.

נראה טוב, אפשר לכתוב קוד.

קישור לגיט – https://github.com/mgershovitz/maya_solves/blob/master/copy_bits.py