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

אופרציות Bitwise (Bitwise Operations) מאפשרות לעבוד ישירות עם ביטים בודדים. פעולות אלו משמשות למשימות כמו קריפטוגרפיה, דחיסה, תקשורת נתונים, ועוד. במדריך זה תלמד אודות האופרטורים AND, OR, XOR, NOT ואודות הזזת ביטים bit shifts.

המרת ספרות מייצוג דצימלי לבינארי והפוך

אנחנו רגילים לייצוג מספרים בדרך עשרונית (דצימלית), באמצעות הספרות 0-9, בעוד מחשבים ברמה הבסיסית ביותר עובדים עם ייצוג בינארי שיש בו רק 2 ספרות: 0 ו-1.

כדי להמיר ספרות מדצימלי לבינארי נשתמש בפונקציה bin(). לדוגמה:

decimal = 10
binary = bin(decimal)  
print(binary) # '0b1010'

פייתון מציין ספרות בינאריות על ידי הדבקת התחילית '0b'.

כדי להסיר את '0b' אפשר להשתמש במניפולציה הבאה:

binary = bin(decimal)[2:]  # '1010'

נמיר מספר נוסף מדצימלי לבינארי:

decimal = 16
binary = bin(decimal)[2:]  # '10000'

בייצוג הבינארי של 10 יש 4 ספרות, בעוד בייצוג הבינארי של 16 יש 5. השוני במספר הספרות עלול להוות בעיה אז הפתרון הוא לרפד משמאל באפסים עד לאורך הרצוי. לדוגמה, נכריח את המספר להיות באורך 8 ביטים:

decimal = 16 
formatted_binary = format(decimal, '08b') # '00010000'

כדי לעשות הפוך, ולהמיר מייצוג בינארי לעשרוני נשתמש בפונקציה int():

binary = '0b10000'
decimal = int(binary, 2)  
print(decimal) # 16

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

אופרטורים bitwise בפייתון

אופרטורים bitwise משמשים להשוואה בין הביטים הבודדים המרכיבים את המספר העשרוני.

האופרטור AND (&): משווה את הביטים ומחזיר 1 רק אם שני הביטים בהשוואה הם 1.

לדוגמה:

n1 = 3   # 011
n2 = 5   # 101
res = n1 & n2
print(format(res, '03b'))  # '001'

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

n1 = 31   # '11111'
n2 = 5     # '101'
res = n1 & n2
print(format(res, '05b')) # '00101'

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

האופרטור OR (|) : משווה ביטים ומחזיר 1 אם לפחות אחד הביטים הוא 1.

לדוגמה:

n1 = 3   # 0011
n2 = 9   # 1001
res = n1 | n2
print(format(res, '04b'))  # '1011'

האופרטור XOR (^) : משווה ביטים ומחזיר 1 אם רק אחד הביטים הוא 1 (והשני 0).

לדוגמה:

n1 = 5   # 0110
n2 = 9   # 1010
res = n1 ^ n2
print(format(res, '04b'))  # '1100'

הטבלה הבאה מסכמת את העניין:

שימוש באופרטור XOR להיפוך הביטים

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

binary  = 0b10010
binary1 = 0b11111
for _ in range(8):
    binary = binary ^ binary1
    print(format(binary, '05b')) 

התוצאה:

01101
10010
01101
10010
01101
10010
01101
10010

• בכל פעם שהלולאה רצה היא החליפה את הביטים מ-0 ל-1, והפוך.

הזזת ביטים

הזזת ביטים (Shift) מאפשרת הכפלה או חלוקה בחזקות של 2 בקלות וביעילות.

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

def print_bin_dec(int):
    print(f"{str(int).ljust(3)} | {format(int,'06b')} | {bin(int)}")

הזזה לשמאל left shift

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

לדוגמה:

n = 10
print_bin_dec(n)   # 10 | 001010 | 0b1010
ls1 = n << 1
print_bin_dec(ls1)  # 20 | 010100 | 0b10100
ls2 = n << 2
print_bin_dec(ls2)  # 40 | 101000 | 0b101000

הזזה לימין right shift

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

לדוגמה:

n = 10
print_bin_dec(n)   # 10  | 001010 | 0b1010
r1 = n >> 1
print_bin_dec(r1)  # 5   | 000101 | 0b101
r2 = n >> 2
print_bin_dec(r2)  # 2   | 000010 | 0b10

הספרה המשמעותית ביותר (MSB) והכי פחות משמעותית (LSB)

הספרה המשמעותית ביותר (Most Significant Bit - MSB) היא הביט השמאלי ביותר בייצוג הבינארי של מספר.

לדוגמה:

• במספר הבינארי 1000, הספרה 1 היא המשמעותית ביותר (MSB).

הספרה הכי פחות משמעותית (Least Significant Bit - LSB) היא הביט הימני ביותר.

לדוגמה:

• במספר הבינארי 1110, הספרה 0 היא הכי פחות משמעותית (LSB).

מספרים signed ו-unsigned

בתכנות מבחינים בין מספרים שהם signed ו-unsigned. בעוד signed יכולים לייצג ערכים חיוביים או שליליים unsigned יכולים לייצג רק ערכים שאינם שליליים (0 וחיוביים).

בפייתון ה-signed number משתמשים בביט המשמעותי ביותר MSB לצורך ציון הסימן, כאשר 0 מייצג מספרים חיוביים ו-1 שליליים.

לדוגמה בייצוג של 8 ביטים:

• 01111111 מייצג את המספר 127
• 10000000 מייצג את המספר -128

הפונקציה הבאה ממחישה כיצד להציג את הייצוג הבינארי של מספרים תוך שימוש ב-mask כדי לשמור רק את הביטים הרלוונטיים:

def print_fixed_bin(num, num_bits=8):
    mask = (1 << num_bits) - 1  # creates a mask 
    fixed_bin = num & mask      # keeps only the relevant bits
    print(f"{str(num).ljust(5)} | {format(fixed_bin, f'0{num_bits}b')} | {bin(fixed_bin)}")

נבדוק:

print_fixed_bin(127)    # 127   | 01111111 | 0b1111111
print_fixed_bin(-128)   # -128  | 10000000 | 0b10000000

נסביר:

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

• היא יוצרת מסכה בינארית המשמשת לבידוד הביטים הרלוונטיים של המספר.
• ואח"כ מפעילה את האופרטור AND בין המספר למסכה מה ששומר את הביטים הרלוונטיים בלבד.

1. יצירת מסיכה באמצעות:

   mask = (1 << num_bits) - 1

   • המסכה נוצרת על ידי הזזה של 1 לשמאל (left shift) כמספר הביטים הרצויים (num_bits).
   • פעולה זו יוצרת מספר בינארי שבו הביט השמאלי ביותר הוא 1, וכל השאר הם 0.
   • חיסור 1 מהמספר משנה את כל הביטים ל־1.
   • לדוגמה, עבור num_bits=8, המסכה היא 11111111.

2. הפעלת אופרטור AND לצורך שמירת הביטים הרלוונטיים:

   fixed_bin = num & mask

   • ביצוע פעולה לוגית של AND בין המספר num למסכה משאירה רק את הביטים המשותפים לשניהם.
   • לדוגמה, אם num הוא -128 (בינארי: 10000000) והמסכה היא 11111111, התוצאה תהיה 10000000.

אופרטור NOT לציון שלילה (~)

האופרטור NOT (~) הופך כל ביט במספר (מ-0 ל-1 ומ-1 ל-0).

לדוגמה:

NOT 10100 = 
    01011

אבל פה צריך להיזהר כי אצל פייתון האופרטור NOT (~) מתייחס למספרים כ-signed מה שאומר שהוא הופך את כל הביטים ואז מתאים לסימן מה שעלול להוביל לתוצאות לא צפויות.

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

def bit_not(num, num_bits=8):
    mask = (1 << num_bits) - 1 # creates a mask with all the bits being 1
    return num ^ mask   # XOR toggles the bits

הפונקציה עובדת בשני שלבים:

1. יוצרת מסכה של מספר בינארי שבו כל הספרות 1.

   לדוגמה, עבור ייצוג בינארי הכולל 8 ביטים:

   11111111

2. משתמשת ב- XOR להפיכת כל הביטים של המספר ביחס למסכה.

   לדוגמה:

   num: 10000000
   mask: 11111111
   XOR: 01111111

ננסה את הפונקציה:

def print_bin_dec(num):
    print(f"{str(num).ljust(3)} | {format(num, '08b')} | {bin(num)}")

n = 128
print_bin_dec(n)            # 128 | 10000000 | 0b10000000
print_bin_dec(bit_not(n))   # 127 | 01111111 | 0b1111111

דוגמה לשימוש : פתרון אתגר תכנותי בעזרת אופרטורים bitwise

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

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

דוגמה:

קלט: n=170
פלט: 4

הסבר:
המחרוזת הבינארית של הקלט היא 010101010, ובה יש 4 ביטים שהם 1.

פתרון ראשון: ספירת הביטים שהם 1 בתוך לולאה

def count_set_bits(num):
    counter = 0
    while num > 0:
        if num & 1:  # Check if the least significant bit is 1
            counter += 1
        num >>= 1    # Shift 1 place to the right to divide by 2
    return counter

נבדוק את הפתרון:

# test cases
test_cases = [
    [0, 0],
    [5, 2],
    [30, 4],
    [137, 3],
    [513729, 11]
]


print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")
for num, expected in test_cases:
    res = count_set_bits(num)
    conclusion = "😄" if res == expected else "😭"
print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")
print("Finito Programa")

הערכת יעילות:

• זמן ריצה: O(log N), כי בכל צעד מחלקים את המספר ב-2.
• מקום: O(1).

פתרון שני: אלגוריתם בריאן קרניגהן

def count_set_bits(num):
    counter = 0
    while num > 0:
        num = num & (num - 1) # Removes the lowest set bit         
        counter += 1
    return counter

נסביר:

• הביטוי num&(num−1) מסיר את הביט שהוא 1 השמאלי ביותר במספר.
  למשל:
  101&100=100
• כל איטרציה מפחיתה את מספר הביטים שהם 1 ב-1, ולכן האלגוריתם יעיל במיוחד עבור מספרים בינאריים עם מעט ביטים שהם 1.

נעבור על כל איטרציה בנפרד כדי לראות את הקוד בפעולה:

Iteration = 1
Num   = 101 (5)
Num-1 = 100 (4)
num&num-1 = 100
Counter = 1

Iteration = 2
Num   = 100 (4)
Num-1 = 011 (3)
num&num-1 = 000
Counter = 2

יעילות:

• זמן ריצה: O(k), כאשר k הוא מספר הביטים שהם 1 במספר.
• מקום: O(1).

שימוש באופרטורים Bitwise לניהול הרשאות

באופרטורים בינאריים משתמשים גם לניהול הרשאות כדוגמת: קריאה, כתיבה והרצה.

בוא נראה איך זה יכול לעבוד בפייתון:

1. הגדרת קבועי ההרשאות

   לכל אחת מ-3 ההרשאות (קריאה, כתיבה, הרצה) מוקצה מיקום במספר בינארי שאורכו 3 ביטים:

   READ = 0b100 # 4 in decimal
   WRITE = 0b010 # 2 in decimal
   EXECUTE = 0b001 # 1 in decimal
   

2. שילוב הרשאות

   שימוש באופרטור OR (|) כדי לשלב הרשאות. לדוגמה, READ | WRITE ייצור הרשאה משולבת לקריאה ולכתיבה (בינארי: 110, עשרוני: 6).

3. בדיקת הרשאות

   שימוש באופרטור AND (&) כדי לבדוק אם הרשאה מסוימת מוגדרת.

הקוד הבא ידגים את העניין:

# Define permissions
READ = 0b100
WRITE = 0b010
EXECUTE = 0b001

# Set initial permissions (Read and Write)
permissions = READ | WRITE
print(f"Permissions: {format(permissions, '03b')}")  # Output: 110

# Check if READ permission is set
if permissions & READ:
    print("Read permission is granted.")

# Check if EXECUTE permission is set
if permissions & EXECUTE:
    print("Execute permission is granted.")
else:
    print("Execute permission is NOT granted.")

# Add EXECUTE permission
permissions |= EXECUTE
print(f"Updated Permissions: {format(permissions, '03b')}")  # Output: 111

נסביר:

• קביעת הרשאות:
  permissions = READ | WRITE מגדיר הרשאות לקריאה ולכתיבה (בינארי: 110).
• בדיקת הרשאות:
  permissions & EXECUTE בודק אם הרשאת הרצה ניתנה.
• עדכון הרשאות:
  permissions |= EXECUTE מוסיף את הרשאת ההרצה, וכתוצאה מכך מתקבל 111 (כל ההרשאות מופעלות).

לסיום: מתי להשתמש בכל אופרטור Bitwise

• AND (&): משמש כאשר רוצים לשמור רק את הביטים שהם 1 בשני המספרים.
• OR (|): מתאים כאשר רוצים לשמור ביטים שהם 1 באחד מהמספרים (או בשניהם).
• XOR (^): טוב לשינוי מצב (toggling) של ביטים.
• NOT (~): הופך ביטים (מ-0 ל-1 ומ-1 ל-0), אך בפייתון יש להשתמש בזהירות.
• אופרטורי הזזה (Shift): משמשים להכפלה או חילוק בחזקות של 2. לדוגמה, x << 1 הוא למעשה x * 2.

השימוש באופרטורים אלה מאפשר גמישות ויעילות רבה בטיפול במספרים בינאריים ובאתגרים תכנותיים מגוונים.

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

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