לדלג לתוכן

10.3 טריקים ביטיים תרגול

תרגול - טריקים ביטיים - bitwise tricks

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

  1. הגדירו את הדגלים הבאים עם #define:
  2. PERM_READ - ביט 0
  3. PERM_WRITE - ביט 1
  4. PERM_EXEC - ביט 2
  5. PERM_ADMIN - ביט 3
  6. כתבו פונקציה void print_permissions(int perms) שמדפיסה אילו הרשאות דלוקות (למשל "READ WRITE").
  7. כתבו פונקציה int grant(int perms, int flag) שמדליקה הרשאה.
  8. כתבו פונקציה int revoke(int perms, int flag) שמכבה הרשאה.
  9. כתבו פונקציה int has_permission(int perms, int flag) שבודקת אם הרשאה דלוקה.
  10. כתבו תוכנית main שיוצרת משתמש עם הרשאות READ + WRITE, מדפיסה אותן, מוסיפה EXEC, מסירה WRITE, ומדפיסה שוב.

תרגול 2 - ספירת ביטים

  1. ממשו את הפונקציה int popcount_naive(unsigned int n) בשיטת הלולאה (עברו על כל 32 ביטים).
  2. ממשו את הפונקציה int popcount_kernighan(unsigned int n) באלגוריתם של Brian Kernighan (השתמשו ב-n &= n - 1).
  3. ממשו גרסה שלישית int popcount_builtin(unsigned int n) שמשתמשת ב-__builtin_popcount.
  4. השוו את שלוש הגרסאות על הערכים: 0, 1, 255, 0xFFFFFFFF, 0xAAAAAAAA.
  5. בונוס: מדדו את הזמן של כל גרסה על לולאה של מיליון קריאות (השתמשו ב-clock() מ-time.h).

תרגול 3 - חזקת 2

  1. כתבו פונקציה int is_power_of_2(unsigned int n) שבודקת אם n הוא חזקה של 2, בעזרת הטריק n & (n-1).
  2. כתבו פונקציה unsigned int next_pow2(unsigned int n) שמחזירה את חזקת 2 הקרובה שגדולה או שווה ל-n.
  3. כתבו פונקציה unsigned int prev_pow2(unsigned int n) שמחזירה את חזקת 2 הקרובה שקטנה או שווה ל-n (רמז: מצאו את הביט הגבוה ביותר עם __builtin_clz).
  4. בדקו על הערכים: 0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 100, 128, 255, 256.

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

  1. כתבו פונקציה unsigned int reverse_bits(unsigned int n) שמהפכת את סדר הביטים (ביט 0 הופך לביט 31, ביט 1 הופך לביט 30, וכו'). ממשו בלולאה.
  2. כתבו פונקציה unsigned int extract_bits(unsigned int n, int start, int len) שמחלצת len ביטים מהמיקום start (למשל, extract_bits(0xFF00, 8, 4) יחזיר 0xF).
  3. כתבו פונקציה unsigned int set_bits(unsigned int n, int start, int len, unsigned int val) שמכניסה את val לתוך n במיקום start באורך len.
  4. כתבו פונקציה void print_binary(unsigned int n) שמדפיסה את הייצוג הבינארי של n (32 ספרות).

תרגול 5 - שדות סיביות ו-endianness

  1. הגדירו struct בשם ip_header עם שדות סיביות שמייצגים את 20 הבתים הראשונים של IP header:
  2. version - 4 ביטים
  3. ihl - 4 ביטים (header length)
  4. tos - 8 ביטים (type of service)
  5. total_length - 16 ביטים
  6. כתבו פונקציה שממלאת את הstruct עם ערכים: version=4, ihl=5, tos=0, total_length=60.
  7. הדפיסו את הגודל של הstruct עם sizeof.
  8. כתבו פונקציה uint16_t my_htons(uint16_t val) שממירה מhost byte order ל-network byte order (big-endian) באמצעות פעולות ביטיות (ללא שימוש ב-htons מהספרייה).
  9. כתבו פונקציה uint32_t my_htonl(uint32_t val) באותו אופן ל-32 ביט.
  10. בדקו שהפונקציות שלכם נותנות את אותה תוצאה כמו htons ו-htonl מהספרייה.