10.3 טריקים ביטיים פתרון

פתרון - טריקים ביטיים - bitwise tricks

פתרון 1 - מערכת הרשאות עם דגלים

#include <stdio.h>

#define PERM_READ   (1 << 0)  // 0001
#define PERM_WRITE  (1 << 1)  // 0010
#define PERM_EXEC   (1 << 2)  // 0100
#define PERM_ADMIN  (1 << 3)  // 1000

void print_permissions(int perms) {
    printf("permissions: ");
    if (perms & PERM_READ)  printf("READ ");
    if (perms & PERM_WRITE) printf("WRITE ");
    if (perms & PERM_EXEC)  printf("EXEC ");
    if (perms & PERM_ADMIN) printf("ADMIN ");
    printf("\n");
}

int grant(int perms, int flag) {
    return perms | flag;
}

int revoke(int perms, int flag) {
    return perms & ~flag;
}

int has_permission(int perms, int flag) {
    return (perms & flag) != 0;
}

int main(void) {
    int perms = PERM_READ | PERM_WRITE;
    printf("initial:\n");
    print_permissions(perms);

    perms = grant(perms, PERM_EXEC);
    printf("\nafter granting EXEC:\n");
    print_permissions(perms);

    perms = revoke(perms, PERM_WRITE);
    printf("\nafter revoking WRITE:\n");
    print_permissions(perms);

    printf("\nhas READ? %s\n", has_permission(perms, PERM_READ) ? "yes" : "no");
    printf("has WRITE? %s\n", has_permission(perms, PERM_WRITE) ? "yes" : "no");
    printf("has EXEC? %s\n", has_permission(perms, PERM_EXEC) ? "yes" : "no");

    return 0;
}

פלט:

initial:
permissions: READ WRITE

after granting EXEC:
permissions: READ WRITE EXEC

after revoking WRITE:
permissions: READ EXEC

has READ? yes
has WRITE? no
has EXEC? yes

---

פתרון 2 - ספירת ביטים

#include <stdio.h>
#include <time.h>

int popcount_naive(unsigned int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += (n >> i) & 1;
    }
    return count;
}

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

int popcount_builtin(unsigned int n) {
    return __builtin_popcount(n);
}

int main(void) {
    unsigned int test_values[] = {0, 1, 255, 0xFFFFFFFF, 0xAAAAAAAA};
    int num_tests = sizeof(test_values) / sizeof(test_values[0]);

    for (int i = 0; i < num_tests; i++) {
        unsigned int n = test_values[i];
        printf("popcount(0x%08X): naive=%d, kernighan=%d, builtin=%d\n",
               n,
               popcount_naive(n),
               popcount_kernighan(n),
               popcount_builtin(n));
    }

    // השוואת ביצועים
    printf("\n--- benchmarks (1M iterations) ---\n");
    clock_t start, end;
    volatile int result;

    start = clock();
    for (int i = 0; i < 1000000; i++)
        result = popcount_naive(0xAAAAAAAA);
    end = clock();
    printf("naive:     %ld us\n", (end - start) * 1000000 / CLOCKS_PER_SEC);

    start = clock();
    for (int i = 0; i < 1000000; i++)
        result = popcount_kernighan(0xAAAAAAAA);
    end = clock();
    printf("kernighan: %ld us\n", (end - start) * 1000000 / CLOCKS_PER_SEC);

    start = clock();
    for (int i = 0; i < 1000000; i++)
        result = popcount_builtin(0xAAAAAAAA);
    end = clock();
    printf("builtin:   %ld us\n", (end - start) * 1000000 / CLOCKS_PER_SEC);

    return 0;
}

הערך 0xAAAAAAAA בבינארי הוא 10101010... - 16 ביטים דלוקים מתוך 32. אלגוריתם Kernighan יבצע 16 איטרציות, הגרסה הנאיבית תמיד 32, ו-builtin פקודה בודדת.

---

פתרון 3 - חזקת 2

#include <stdio.h>

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

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

unsigned int prev_pow2(unsigned int n) {
    if (n == 0) return 0;
    // מיקום הביט הגבוה ביותר
    int highest_bit = 31 - __builtin_clz(n);
    return 1u << highest_bit;
}

int main(void) {
    unsigned int values[] = {0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 100, 128, 255, 256};
    int n = sizeof(values) / sizeof(values[0]);

    printf("%-6s %-10s %-10s %-10s\n", "n", "is_pow2", "next_pow2", "prev_pow2");
    printf("--------------------------------------\n");

    for (int i = 0; i < n; i++) {
        unsigned int v = values[i];
        printf("%-6u %-10s %-10u %-10u\n",
               v,
               is_power_of_2(v) ? "yes" : "no",
               next_pow2(v),
               prev_pow2(v));
    }

    return 0;
}

פלט (חלקי):

n      is_pow2    next_pow2  prev_pow2
--------------------------------------
0      no         1          0
1      yes        1          1
2      yes        2          2
3      no         4          2
4      yes        4          4
5      no         8          4
100    no         128        64
128    yes        128        128
255    no         256        128
256    yes        256        256

הפונקציה prev_pow2 עובדת כך: __builtin_clz(n) מחזיר את מספר האפסים המובילים. אם n=100 (01100100), יש 25 אפסים מובילים, אז הביט הגבוה הוא 31-25=6. חזקת 2 הקרובה מלמטה היא 1 << 6 = 64.

---

פתרון 4 - מניפולציות ביטיות

#include <stdio.h>

void print_binary(unsigned int n) {
    for (int i = 31; i >= 0; i--) {
        printf("%d", (n >> i) & 1);
        if (i % 8 == 0) printf(" ");
    }
    printf("\n");
}

unsigned int reverse_bits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

unsigned int extract_bits(unsigned int n, int start, int len) {
    // יוצר מסכה של len ביטים דלוקים
    unsigned int mask = (1u << len) - 1;
    // מזיז ימינה ל-start ומחיל את המסכה
    return (n >> start) & mask;
}

unsigned int set_bits(unsigned int n, int start, int len, unsigned int val) {
    unsigned int mask = (1u << len) - 1;
    // מנקה את הביטים הישנים
    n &= ~(mask << start);
    // מכניס את הערך החדש
    n |= (val & mask) << start;
    return n;
}

int main(void) {
    // reverse_bits
    unsigned int x = 0x80000001; // 10000...0001
    printf("reverse_bits:\n");
    printf("  input:  "); print_binary(x);
    printf("  output: "); print_binary(reverse_bits(x));

    // extract_bits
    printf("\nextract_bits:\n");
    unsigned int val = 0xFF00;
    printf("  extract_bits(0x%X, 8, 4) = 0x%X\n",
           val, extract_bits(val, 8, 4)); // 0xF

    printf("  extract_bits(0x%X, 8, 8) = 0x%X\n",
           val, extract_bits(val, 8, 8)); // 0xFF

    // set_bits
    printf("\nset_bits:\n");
    unsigned int n = 0x0000;
    n = set_bits(n, 4, 4, 0xA); // מכניס 0xA בביטים 4-7
    printf("  set_bits(0, 4, 4, 0xA) = 0x%X\n", n); // 0xA0

    n = set_bits(n, 0, 4, 0x5); // מכניס 0x5 בביטים 0-3
    printf("  set_bits(0xA0, 0, 4, 0x5) = 0x%X\n", n); // 0xA5

    return 0;
}

ההסבר ל-extract_bits: המסכה (1u << len) - 1 יוצרת len ביטים של 1. למשל, (1 << 4) - 1 = 0b1111 = 0xF. אחרי שמזיזים את n ימינה ב-start, מחילים AND עם המסכה כדי לקחת רק את הביטים שרוצים.

ההסבר ל-set_bits: קודם מנקים את הביטים הישנים (AND עם NOT של המסכה המוזזת), ואז מכניסים את הערך החדש (OR עם הערך מוזז).

---

פתרון 5 - שדות סיביות ו-endianness

#include <stdio.h>
#include <stdint.h>
#include <arpa/inet.h>

struct ip_header {
    unsigned int version      : 4;
    unsigned int ihl          : 4;
    unsigned int tos          : 8;
    unsigned int total_length : 16;
};

void fill_ip_header(struct ip_header *hdr) {
    hdr->version = 4;
    hdr->ihl = 5;
    hdr->tos = 0;
    hdr->total_length = 60;
}

uint16_t my_htons(uint16_t val) {
    return ((val & 0xFF) << 8) | ((val >> 8) & 0xFF);
}

uint32_t my_htonl(uint32_t val) {
    return ((val & 0x000000FF) << 24) |
           ((val & 0x0000FF00) << 8)  |
           ((val & 0x00FF0000) >> 8)  |
           ((val & 0xFF000000) >> 24);
}

int main(void) {
    // חלק 1-3: bit fields
    struct ip_header hdr;
    fill_ip_header(&hdr);

    printf("IP header:\n");
    printf("  version = %u\n", hdr.version);
    printf("  ihl = %u\n", hdr.ihl);
    printf("  tos = %u\n", hdr.tos);
    printf("  total_length = %u\n", hdr.total_length);
    printf("  sizeof(ip_header) = %lu bytes\n", sizeof(hdr));

    // חלק 4-6: endianness
    printf("\nhtons comparison:\n");
    uint16_t val16 = 0x1234;
    printf("  my_htons(0x%04X) = 0x%04X\n", val16, my_htons(val16));
    printf("  htons(0x%04X)    = 0x%04X\n", val16, htons(val16));

    printf("\nhtonl comparison:\n");
    uint32_t val32 = 0x12345678;
    printf("  my_htonl(0x%08X) = 0x%08X\n", val32, my_htonl(val32));
    printf("  htonl(0x%08X)    = 0x%08X\n", val32, htonl(val32));

    return 0;
}

ההסבר ל-my_htons: לוקחים את הבית הנמוך (val & 0xFF) ומזיזים אותו 8 ביטים שמאלה, ואת הבית הגבוה (val >> 8) מזיזים ימינה. בעצם מחליפים את סדר שני הבתים.

ההסבר ל-my_htonl: אותו עיקרון אבל עם 4 בתים. כל בית עובר למיקום ה"מראה" שלו:
- בית 0 (הנמוך) עובר למיקום 3 (הגבוה)
- בית 1 עובר למיקום 2
- בית 2 עובר למיקום 1
- בית 3 (הגבוה) עובר למיקום 0 (הנמוך)