איך מספרים חיים בתוך המחשב

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

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

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

בסיס 10 לעומת בסיס 2

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

583 = 5*100 + 8*10 + 3*1
    = 5*10^2 + 8*10^1 + 3*10^0

בבינארי העיקרון זהה, אבל כל מיקום מבוסס על חזקה של 2:

... 32 16 8 4 2 1

לדוגמה:

1011_2

נמקם את הספרות מול ערכי העמודות:

ערך:   8 4 2 1
ביט:   1 0 1 1

ולכן:

1011_2 = 8 + 0 + 2 + 1 = 11_10

הספרה הימנית ביותר מייצגת תמיד את `2^0`, שערכו 1. משמאלה נמצאות `2^1`, `2^2`, `2^3` וכן הלאה.

המרה מעשרוני לבינארי

אחת השיטות הנוחות היא לפרק את המספר לחזקות של 2.

נמיר את 45:

45 = 32 + 8 + 4 + 1

נכתוב את העמודות:

32 16 8 4 2 1

ונסמן `1` במקום שבו השתמשנו בערך, ו-`0` במקום שלא:

32 16 8 4 2 1
 1  0 1 1 0 1

לכן:

45_10 = 101101_2

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

המרה מבינארי לעשרוני

ניקח את:

1010110_2

נפרק לפי העמודות:

64 32 16 8 4 2 1
 1  0  1 0 1 1 0

ולכן:

64 + 16 + 4 + 2 = 86

כלומר:

1010110_2 = 86_10

חיבור וחיסור בינאריים

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

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

התוצאה `10` פירושה שכותבים `0` בעמודה הנוכחית ומעבירים `1` לעמודה הבאה.

  1011
+ 0101
------
 10000

בחיסור, כאשר צריך לחשב `0-1`, שואלים מהעמודה שמשמאל. הביט שנשאל הופך בעמודה הנוכחית ל-`10_2`, כלומר לשתי יחידות.

  10101
- 00110
-------
  01111

בדיקה עשרונית:

21 - 6 = 15
01111_2 = 15

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

הזזת ביטים ב-Java

ב-Java קיימים אופרטורים שמזיזים את כל הביטים ימינה או שמאלה.

הזזה שמאלה: `<<`

int result = 13 << 1;

הייצוג של 13 הוא:

001101

לאחר הזזה אחת שמאלה:

011010

כלומר:

13 << 1 = 26

באופן כללי, הזזה שמאלה ב-`n` מקומות שקולה בדרך כלל לכפל ב-`2^n`:

x << 1  ~= x * 2
x << 2  ~= x * 4
x << 3  ~= x * 8

הסימן `~=` חשוב: השוויון תקף רק כאשר לא נאבדים ביטים ואין overflow שמשנה את התוצאה.

הזזה ימינה: `>>`

במספר חיובי, הזזה ימינה שקולה בדרך כלל לחלוקה שלמה בחזקה של 2:

int result = 29 >> 1; // 14

בבינארי:

11101 -> 01110

הביט הימני שנזרק ייצג את השארית. במקרה הזה הוא היה `1`, ולכן:

29 / 2 = 14 ושארית 1

פעולות לוגיות על ביטים

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

נשתמש במספרים:

A = 10110
B = 01101

AND: `&`

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

  10110
& 01101
-------
  00100

OR: `|`

התוצאה היא `1` כאשר לפחות אחד מהביטים הוא `1`.

  10110
| 01101
-------
  11111

XOR: `^`

התוצאה היא `1` כאשר הביטים שונים.

  10110
^ 01101
-------
  11011

ההבדל המרכזי בין OR ל-XOR מופיע כאשר שני הביטים הם `1`:

1 OR  1 = 1
1 XOR 1 = 0

NOT: `~`

NOT הופך כל ביט:

0 -> 1
1 -> 0

ברוחב תאורטי של חמישה ביטים:

~10110 = 01001

אבל `int` ב-Java מכיל 32 ביטים, ולכן `~` הופך את כל 32 הביטים, גם את אלה שאינם מוצגים בדוגמה הקצרה.

שימוש מעשי: שמירת הרשאות בתוך מספר אחד

נניח שלמערכת יש ארבע הרשאות:

private static final int READ    = 1;      // 0001
private static final int WRITE   = 1 << 1; // 0010
private static final int EXECUTE = 1 << 2; // 0100
private static final int ADMIN   = 1 << 3; // 1000

המספר:

0101

מייצג שתי הרשאות פעילות:

READ    = 1
WRITE   = 0
EXECUTE = 1
ADMIN   = 0

כלומר, למשתמש יש הרשאות קריאה והרצה.

הפעלת הרשאה עם OR

permissions |= WRITE;

0101 | 0010 = 0111

בדיקת הרשאה עם AND

boolean canExecute = (permissions & EXECUTE) != 0;

אם תוצאת ה-AND אינה אפס, הביט קיים.

כיבוי הרשאה עם AND ו-NOT

permissions &= ~READ;

פעולת `~READ` יוצרת מסכה שבה הביט של READ הוא `0` ושאר הביטים הם `1`. פעולת AND מכבה רק את READ.

החלפת מצב עם XOR

permissions ^= EXECUTE;

אם EXECUTE היה פעיל, הוא יכבה. אם היה כבוי, הוא יופעל.

בדיקת הרשאה אחת, לפחות אחת או את כולן

נניח שהמסכה מכילה שתי הרשאות:

int mask = READ | WRITE;

כדי לבדוק אם קיימת לפחות הרשאה אחת:

boolean hasAny = (permissions & mask) != 0;

כדי לבדוק אם קיימות כל ההרשאות שבמסכה:

boolean hasAll = (permissions & mask) == mask;

אלה שתי שאלות שונות.

permissions = 0101
mask        = 0011

תוצאת AND:

0101 & 0011 = 0001

לכן:

hasAny = true
hasAll = false

יש הרשאה משותפת אחת, READ, אבל WRITE חסרה.

רוחב קבוע ו-overflow

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

נניח שמותר לשמור ארבעה ביטים בלבד:

1101_2 = 13

הזזה שמאלה נותנת תוצאה מלאה:

1101 << 1 = 11010_2 = 26

אבל `11010` דורש חמישה ביטים. אם מותר לשמור רק ארבעה, הביט השמאלי נזרק:

11010
 ↓↓↓↓
1010

התוצאה שנשמרת היא:

1010_2 = 10

הביט שנמחק ייצג את הערך 16:

26 - 16 = 10

זהו overflow: הפעולה התבצעה, אבל לא היה מספיק מקום לייצג את התוצאה המלאה.

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

מספרים שליליים: ההבדל בין `>>` ל-`>>>`

Java מספקת שני אופרטורים להזזה ימינה.

הזזה אריתמטית: `>>`

האופרטור `>>` משכפל משמאל את ביט הסימן.

במספר שלילי, ביט הסימן הוא `1`, ולכן המספר נשאר שלילי:

-8 >> 1 == -4

הזזה לוגית: `>>>`

האופרטור `>>>` מכניס תמיד `0` משמאל, גם כאשר המספר שלילי.

-8 >>> 1 == 2147483644

התוצאה גדולה וחיובית משום שהביט השמאלי הפך ל-`0`, ושאר הביטים נשארו פעילים.

-16 >> 2  == -4
-16 >>> 2 == 1073741820

מדוע `/` ו-`>>` שונים במספר שלילי אי-זוגי?

נבחן:

-11 / 2
-11 >> 1

התוצאה המתמטית היא:

-11 / 2 = -5.5

חלוקת מספרים שלמים באמצעות `/` ב-Java נחתכת לכיוון אפס:

-11 / 2 == -5

לעומת זאת, הזזה אריתמטית ימינה מתנהגת במקרה הזה כמו עיגול כלפי מטה:

-11 >> 1 == -6

לכן אסור להחליף אוטומטית חלוקה ב-2 בהזזה ימינה כאשר הערך עלול להיות שלילי.

חשוב גם לזכור: `//` אינו אופרטור חילוק ב-Java. הוא פותח הערה עד סוף השורה.

int result = -11 / 2; // התוצאה היא -5

ניסוי מלא ב-Java

public class BinaryExperiment {

    private static final int READ    = 1;
    private static final int WRITE   = 1 << 1;
    private static final int EXECUTE = 1 << 2;
    private static final int ADMIN   = 1 << 3;

    public static void main(String[] args) {
        int number = 45;

        System.out.println(
                "45 in binary: " + Integer.toBinaryString(number)
        );

        int parsed = Integer.parseInt("101101", 2);
        System.out.println("101101 in decimal: " + parsed);

        System.out.println("13 << 2: " + (13 << 2));
        System.out.println("29 >> 1: " + (29 >> 1));

        int permissions = READ | EXECUTE;
        printPermissions("Initial", permissions);

        permissions |= WRITE;
        printPermissions("Enable WRITE", permissions);

        permissions ^= EXECUTE;
        printPermissions("Toggle EXECUTE", permissions);

        permissions &= ~READ;
        printPermissions("Disable READ", permissions);

        permissions |= ADMIN;
        printPermissions("Enable ADMIN", permissions);

        int mask = WRITE | ADMIN;

        boolean hasAny = (permissions & mask) != 0;
        boolean hasAll = (permissions & mask) == mask;

        System.out.println("Has any required permission: " + hasAny);
        System.out.println("Has all required permissions: " + hasAll);

        System.out.println("-11 / 2: " + (-11 / 2));
        System.out.println("-11 >> 1: " + (-11 >> 1));
        System.out.println("-16 >>> 2: " + (-16 >>> 2));
    }

    private static void printPermissions(String title, int value) {
        String binary = String.format(
                "%4s",
                Integer.toBinaryString(value)
        ).replace(' ', '0');

        System.out.println(title + ": " + binary + " (" + value + ")");
    }
}

טעויות נפוצות

הטעות הראשונה היא לקרוא מספר בינארי כאילו היה מספר עשרוני. `1011_2` אינו אלף ואחת עשרה, אלא 11.

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

במסכות ביטים, הבדיקה:

(permissions & mask) != 0

בודקת אם קיים לפחות ביט משותף אחד. היא אינה בודקת שכל הביטים במסכה קיימים. לבדיקת כולם יש להשתמש ב:

(permissions & mask) == mask

בנוסף, יש להבחין בין תוצאת פעולת AND, שהיא מספר, לבין תוצאת ההשוואה ל-0, שהיא `boolean`.

לבסוף, פעולת `~` ב-Java אינה הופכת רק את הביטים שאנחנו מציגים על המסך. היא הופכת את כל הביטים של הטיפוס.

סיכום

בינארי הוא אותה שיטה מיקומית שאנחנו מכירים מבסיס 10, רק עם חזקות של 2 ועם הספרות `0` ו-`1`.

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

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

ברגע שרואים מספר כמערכת של ביטים נפרדים, פעולות שנראו בעבר מסתוריות, כמו `&`, `|`, `^`, `~`, `<<`, `>>` ו-`>>>`, הופכות לכלים ברורים ושימושיים.