תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

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

מחבר:
בתאריך:

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

Bitwise operations

 

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

אנחנו רגילים לייצוג מספרים בדרך עשרונית (דצימלית), באמצעות הספרות 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 ספרות אז כדי שיהיה לנו נוח לראות מה קורה נרפד את המספר הקצר ביותר באפסים משמאל באופן כזה שהאורך של שני המספרים ישתווה:

binary

decimal

1

1

1

1

1

31

1

0

1

0

0

5

1

0

1

0

0

&

האופרטור 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

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

אופרטור

מסומן

מה עושה?

לדוגמה

AND

&

רק אם שני הביטים הם 1 התוצאה תהיה 1

1 & 1 → 1

1 & 0 → 0

OR

|

אפילו אם אחד הביטים הוא 1 התוצאה תהיה 1

1 | 1 → 1

1 | 0 → 1

0 | 0 → 0

XOR

^

אם רק אחד הביטים הוא 1 (והשני 0) התוצאה תהיה 1

1 | 1 → 0

1 | 0 → 1

0 | 0 → 0

 

שימוש באופרטור 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)
ls1 = n << 1
print_bin_dec(ls1)
ls2 = n << 2
print_bin_dec(ls2)

התוצאה:

10  | 001010 | 0b1010
20  | 010100 | 0b10100
40  | 101000 | 0b101000

 

הזזה לימין right shift

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

לדוגמה:

n = 10
print_bin_dec(n) 
r1 = n >> 1
print_bin_dec(r1)
r2 = n >> 2
print_bin_dec(r2)

התוצאה:

10  | 001010 | 0b1010
5   | 000101 | 0b101
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)
print_fixed_bin(-128)

התוצאה:

127   | 01111111 | 0b1111111
-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

ננסה את הפונקציה bit_not():

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

n = 128
print_bin_dec(n)
print_bin_dec(bit_not(n))

התוצאה:

128 | 10000000 | 0b10000000
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

נסביר:

  • הפונקציה count_set_bits(num) מקבלת את הפרמטר `num` מספר דצימלי שעליה למצוא את מספר הביטים שהם 1 בייצוגו הבינארי.

  • המשתנה `counter` מונה את מספר הביטים שהם 1. נאתחל את ערכו ל-0.

  • לולאת while רצה כל עוד הערך של `num` גדול מאפס.
    במסגרתה:

    1. if num & 1:
          counter += 1

      בודק האם המספר השמאלי ביותר בייצוג הבינארי הוא 1, ואם זה המצב אז מוסיף 1 למונה.

    2. num >>= 1

      מזיז לימין פעם 1 כדי לחלק ב-2.

  • הפונקציה מחזירה את ערך המונה `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")

התוצאה:

Result    Expected  Conclusion
------------------------------
0         0         😄
2         2         😄
4         4         😄
3         3         😄
11        11        😄
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 שזה בעשרוני 7 (כל ההרשאות מופעלות).

 

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

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

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

 

מדריכים נוספים שעשויים לעניין אותך

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

ניהול הרשאות, משתמשים וקבוצות בלינוקס

אלגוריתם חיפוש בינארי - מהבנה ליישום

 

לכל המדריכים בסדרה ללימוד פייתון

 

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

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

 

 

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

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

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

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

מתי הוקמה המדינה?