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

הקדמה¶

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

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

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

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

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

x |= (1 << k);  // turns on bit number k

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

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

x &= ~(1 << k);  // turns off bit number k

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

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

x ^= (1 << k);  // toggles bit number k

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

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

int bit = (x >> k) & 1;  // returns 0 or 1 - the value of bit k

או:

if (x & (1 << k)) {
    // bit k is set
}

מסכות סיביות ודגלים - 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 - read and write

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

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

הדלקת דגל:

perms |= FLAG_EXEC;  // now 0111

כיבוי דגל:

perms &= ~FLAG_WRITE;  // now 0101

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

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

// from <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, so it's a power of 2!

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

n     = 00010100  (20)
n - 1 = 00010011  (19)
n & (n-1) = 00010000  ->  not 0, so it's not a power of 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  (the original value of a!)
a ^= b  ->  a = 6^5 = 3  (the original value of b!)

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

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

int my_abs(int x) {
    int mask = x >> 31;         // 0 if x >= 0, -1 (all bits 1) if 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;  // turns off the lowest set bit
        count++;
    }
    return count;
}

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

דוגמה:

n = 01010100
n & (n-1) = 01010100 & 01010011 = 01010000  -> we turned off the low bit (bit 2)
n & (n-1) = 01010000 & 01001111 = 01000000  -> we turned off bit 4
n & (n-1) = 01000000 & 00111111 = 00000000  -> we turned off bit 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);   // returns the position of the lowest set bit (1-based), 0 if x==0
int tz = __builtin_ctz(x);    // count trailing zeros - the number of zeros on the right (0-based)

דוגמה:

x = 01010100  (84)
__builtin_ffs(x) = 3    (bit 2, 1-based = 3)
__builtin_ctz(x) = 2    (2 zeros on the right)

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

int lz = __builtin_clz(x);   // count leading zeros - the number of zeros on the left

דוגמה:

x = 01010100  (84, in 32 bits: 00000000 00000000 00000000 01010100)
__builtin_clz(x) = 25   (25 zeros on the left)
// the highest bit is bit 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;  // one bit
    unsigned int write   : 1;
    unsigned int execute : 1;
    unsigned int level   : 4;  // 4 bits (values 0-15)
    unsigned int flags   : 9;  // 9 bits
};

כל ה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);   // reverses byte order in 32 bits
uint64_t swapped = __builtin_bswap64(x);   // reverses byte order in 64 bits

טבלת 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 כשעובדים עם נתונים בינאריים מרשת או מקובץ