טריקים ביטיים - bitwise tricks¶

הקדמה¶

בפרק 0 למדנו על מערכות ספירה בינאריות ועל האופרטורים הביטיים הבסיסיים: AND (&), OR (|), XOR (^), NOT (~), הזזה שמאלה (<<), הזזה ימינה (>>). באסמבלי (פרקים 1-2) השתמשנו בפקודות כמו and, or, xor, shl, shr.

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

בדיקה, הדלקה, כיבוי, והיפוך של ביט¶

ארבע הפעולות הבסיסיות ביותר:

הדלקת ביט - set bit¶

x |= (1 << k);  // מדליק את ביט מספר k

הלוגיקה: 1 << k יוצר מספר שכל הביטים שלו 0 מלבד ביט k. OR עם x מדליק את ביט k בלי לשנות את שאר הביטים.

כיבוי ביט - clear bit¶

x &= ~(1 << k);  // מכבה את ביט מספר k

הלוגיקה: ~(1 << k) יוצר מספר שכל הביטים שלו 1 מלבד ביט k. AND עם x מכבה את ביט k בלי לשנות את שאר הביטים.

היפוך ביט - toggle bit¶

x ^= (1 << k);  // הופך את ביט מספר k

הלוגיקה: XOR עם 1 הופך ביט (0 הופך ל-1, 1 הופך ל-0). XOR עם 0 לא משנה.

בדיקת ביט - check bit¶

int bit = (x >> k) & 1;  // מחזיר 0 או 1 - הערך של ביט k

או:

if (x & (1 << k)) {
    // ביט k דלוק
}

מסכות סיביות ודגלים - bit masks and flags¶

אחד השימושים הכי נפוצים של ביטים הוא ייצוג דגלים (flags) - אוסף של ערכי true/false ארוזים במספר אחד:

#define FLAG_READ   (1 << 0)  // 0001
#define FLAG_WRITE  (1 << 1)  // 0010
#define FLAG_EXEC   (1 << 2)  // 0100
#define FLAG_HIDDEN (1 << 3)  // 1000

עכשיו אפשר לשלב כמה דגלים ביחד:

int perms = FLAG_READ | FLAG_WRITE;  // 0011 - קריאה וכתיבה

בדיקה אם דגל מסוים דלוק:

if (perms & FLAG_READ) {
    printf("read permission granted\n");
}

הדלקת דגל:

perms |= FLAG_EXEC;  // עכשיו 0111

כיבוי דגל:

perms &= ~FLAG_WRITE;  // עכשיו 0101

ככה זה עובד בעולם האמיתי¶

הרשאות קבצים בלינוקס (שלמדנו בפרק 5) עובדות בדיוק ככה:

// מתוך <fcntl.h>
#define O_RDONLY   0x0000
#define O_WRONLY   0x0001
#define O_RDWR     0x0002
#define O_CREAT    0x0040
#define O_TRUNC    0x0200
#define O_APPEND   0x0400

כשאנחנו כותבים:

int fd = open("file.txt", O_WRONLY | O_CREAT | O_TRUNC, 0644);

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

גם mmap (פרק 5.7) עובד ככה:

void *p = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

בדיקה אם מספר הוא חזקה של 2¶

int is_power_of_2(unsigned int n) {
    return n && !(n & (n - 1));
}

למה זה עובד? מספר שהוא חזקה של 2 יש לו בדיוק ביט אחד דלוק:

1   = 00000001
2   = 00000010
4   = 00000100
8   = 00001000
16  = 00010000

כש-n הוא חזקה של 2, אז n - 1 הופך את כל הביטים שמתחת לביט הדלוק:

n     = 00010000
n - 1 = 00001111
n & (n-1) = 00000000  ->  0, אז זה חזקה של 2!

אם n לא חזקה של 2:

n     = 00010100  (20)
n - 1 = 00010011  (19)
n & (n-1) = 00010000  ->  לא 0, אז זה לא חזקה של 2

הבדיקה n && מוודאת ש-n לא אפס (כי 0 הוא לא חזקה של 2, אבל 0 & (-1) הוא 0).

החלפה ללא משתנה זמני - swap without temp¶

a ^= b;
b ^= a;
a ^= b;

טריק קלאסי שמבוסס על התכונה: x ^ x = 0 ו-x ^ 0 = x.

נעקוב (נניח a=5, b=3):

a ^= b  ->  a = 5^3 = 6
b ^= a  ->  b = 3^6 = 5  (הערך המקורי של a!)
a ^= b  ->  a = 6^5 = 3  (הערך המקורי של b!)

בפרקטיקה, לא כדאי להשתמש בזה. משתנה זמני פשוט יותר לקריאה, והקומפיילר ממילא מבצע את האופטימיזציה בשבילנו. הטריק גם נשבר אם a ו-b מצביעים לאותו מקום בזיכרון (a ^= a נותן 0).

ערך מוחלט ללא פיצול - absolute value without branching¶

int my_abs(int x) {
    int mask = x >> 31;         // 0 אם x >= 0, -1 (כל הביטים 1) אם x < 0
    return (x ^ mask) - mask;
}

איך זה עובד?

אם x חיובי: mask = 0, אז (x ^ 0) - 0 = x
אם x שלילי: mask = -1 = 0xFFFFFFFF, אז (x ^ 0xFFFFFFFF) - (-1) = (~x) + 1 = -x

הביטוי (~x) + 1 הוא בדיוק השלילה של x בייצוג two's complement (למדנו בפרק 0).

למה ללא פיצול? כי פיצולים (branches) יכולים להאט את הcache pipeline של המעבד (למדנו על branch prediction בפרק 8). בקוד קריטי לביצועים, מניעת פיצולים יכולה לשפר מהירות.

ספירת ביטים דלוקים - popcount¶

שיטה נאיבית - לולאה¶

int popcount_naive(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

זמן ריצה: O(32) - תמיד 32 איטרציות (או מספר הביטים בטיפוס).

אלגוריתם של Brian Kernighan¶

int popcount_kernighan(unsigned int n) {
    int count = 0;
    while (n) {
        n &= n - 1;  // מכבה את הביט הדלוק הנמוך ביותר
        count++;
    }
    return count;
}

הטריק: n & (n - 1) מכבה את הביט הדלוק הנמוך ביותר. כל איטרציה מכבה ביט אחד, אז מספר האיטרציות שווה למספר הביטים הדלוקים.

דוגמה:

n = 01010100
n & (n-1) = 01010100 & 01010011 = 01010000  -> כיבינו את הביט הנמוך (ביט 2)
n & (n-1) = 01010000 & 01001111 = 01000000  -> כיבינו את ביט 4
n & (n-1) = 01000000 & 00111111 = 00000000  -> כיבינו את ביט 6

3 איטרציות, 3 ביטים דלוקים.

פונקציית builtin¶

int count = __builtin_popcount(x);     // unsigned int
int count = __builtin_popcountl(x);    // unsigned long
int count = __builtin_popcountll(x);   // unsigned long long

הקומפיילר מתרגם את זה לפקודת מעבד popcnt אם המעבד תומך (רוב המעבדים המודרניים תומכים).

מציאת הביט הדלוק הנמוך/גבוה ביותר¶

ביט דלוק נמוך ביותר - find first set¶

int pos = __builtin_ffs(x);   // מחזיר מיקום הביט הדלוק הנמוך ביותר (1-based), 0 אם x==0
int tz = __builtin_ctz(x);    // count trailing zeros - מספר האפסים מימין (0-based)

דוגמה:

x = 01010100  (84)
__builtin_ffs(x) = 3    (ביט 2, 1-based = 3)
__builtin_ctz(x) = 2    (2 אפסים מימין)

ביט דלוק גבוה ביותר - find last set¶

int lz = __builtin_clz(x);   // count leading zeros - מספר האפסים משמאל

דוגמה:

x = 01010100  (84, ב-32 ביט: 00000000 00000000 00000000 01010100)
__builtin_clz(x) = 25   (25 אפסים משמאל)
// הביט הגבוה ביותר הוא ביט 31 - 25 = 6

שימו לב: __builtin_ctz(0) ו-__builtin_clz(0) הם undefined behavior! תמיד בדקו ש-x לא 0 לפני הקריאה.

עיגול למעלה לחזקת 2¶

פונקציה שמקבלת מספר ומחזירה את חזקת 2 הקרובה שגדולה ממנו או שווה לו:

unsigned int next_power_of_2(unsigned int n) {
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;
}

איך זה עובד? אחרי n--, אנחנו "מורחים" את הביט הגבוה ביותר ימינה עד שכל הביטים מתחתיו דלוקים:

n = 01010100  (84)
n-- = 01010011
n |= n>>1  ->  01111011
n |= n>>2  ->  01111111
n |= n>>4  ->  01111111
...
n++ = 10000000 (128)

הקרנל של לינוקס משתמש בטכניקה הזו בפונקציה roundup_pow_of_two.

שדות סיביות בסטראקטים - bit fields¶

C מאפשרת להגדיר שדות בתוך struct שתופסים מספר ביטים מוגדר:

struct permissions {
    unsigned int read    : 1;  // ביט אחד
    unsigned int write   : 1;
    unsigned int execute : 1;
    unsigned int level   : 4;  // 4 ביטים (ערכים 0-15)
    unsigned int flags   : 9;  // 9 ביטים
};

כל הstruct הזה תופס 16 ביט בלבד (2 בתים), במקום 5 int-ים (20 בתים).

struct permissions p;
p.read = 1;
p.write = 0;
p.execute = 1;
p.level = 7;
p.flags = 0x1F;

printf("read=%d, write=%d, exec=%d, level=%d\n",
       p.read, p.write, p.execute, p.level);

שימו לב: סדר הביטים ב-bit fields תלוי בקומפיילר ובארכיטקטורה (implementation-defined). אל תשתמשו ב-bit fields כשאתם צריכים לשלוט בסדר המדויק של הביטים (למשל, בפרוטוקולי רשת). במקרה כזה, השתמשו במסכות ביטיות.

סדר בתים - endianness¶

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

ליטל אנדיאן - little-endian: הבית הפחות משמעותי ראשון (x86, x86_64)
ביג אנדיאן - big-endian: הבית המשמעותי ביותר ראשון (סדר רשת, מעבדי SPARC)

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

#include <arpa/inet.h>

uint32_t host_val = 0x12345678;
uint32_t net_val  = htonl(host_val);  // host to network long
uint16_t net_port = htons(8080);      // host to network short

uint32_t back = ntohl(net_val);       // network to host long
uint16_t port = ntohs(net_port);      // network to host short

אפשר גם להפוך endianness ידנית עם intrinsics:

uint32_t swapped = __builtin_bswap32(x);   // הופך סדר בתים ב-32 ביט
uint64_t swapped = __builtin_bswap64(x);   // הופך סדר בתים ב-64 ביט

טבלת intrinsics נפוצים¶

פונקציה	תיאור
`__builtin_popcount(x)`	ספירת ביטים דלוקים
`__builtin_ctz(x)`	ספירת אפסים מימין (trailing zeros)
`__builtin_clz(x)`	ספירת אפסים משמאל (leading zeros)
`__builtin_ffs(x)`	מיקום הביט הדלוק הראשון (1-based)
`__builtin_parity(x)`	1 אם מספר ביטים דלוקים אי-זוגי
`__builtin_bswap32(x)`	היפוך סדר בתים (32-ביט)
`__builtin_bswap64(x)`	היפוך סדר בתים (64-ביט)

כל הפונקציות האלו מתורגמות לפקודת מעבד בודדת (או כמה פקודות) - הן מהירות מאוד בהשוואה למימוש בלולאה.

סיכום¶

פעולות ביטיות הן הבסיס של תכנות מערכות - דגלים, הרשאות, פרוטוקולים, ומבני נתונים קומפקטיים
הדלקה (|=), כיבוי (&= ~), היפוך (^=), ובדיקה (&) של ביטים הן ארבע הפעולות הבסיסיות
n & (n-1) מכבה את הביט הנמוך ביותר - שימושי לbrian kernighan ולבדיקת חזקה של 2
שדות סיביות (bit fields) חוסכים זיכרון אבל תלויים במימוש
פונקציות builtin כמו __builtin_popcount מהירות יותר ממימוש ידני
תמיד שימו לב ל-endianness כשעובדים עם נתונים בינאריים מרשת או מקובץ