کمپیوٹر سسٹم CSAPP کی گہری تفہیم: ڈیٹا لاب نوٹ

Deep Understanding Computer System Csapp



فہرست کا خانہ

مواد اجزاء اور فلوٹنگ پوائنٹ نمبروں کا بٹ لیول آپریشن ہے۔

  1. بٹ اینڈ
    ڈی مورگن کا قانون استعمال کریں۔
/* * bitAnd - x&y using only ~ and | * Example: bitAnd(6, 5) = 4 * Legal ops: ~ | * Max ops: 8 * Rating: 1 */ int bitAnd(int x, int y) ~y)
  1. getByte
    پہلے دائیں طرف منتقل کریں ، اور آخر میں بائیں ٹارگٹ بائٹ کو منتقل کرنے کے لئے 0xFF استعمال کریں۔
/* * getByte - Extract byte n from word x * Bytes numbered from 0 (LSB) to 3 (MSB) * Examples: getByte(0x12345678,1) = 0x56 * Legal ops: ! ~ & ^ | + <> * Max ops: 6 * Rating: 2 */ int getByte(int x, int n) { int tmp = x >> ((n) << 3) tmp = tmp & 0xFF return tmp }
  1. منطقی شفٹ
    پہلے ، ہمیں منطقی شفٹ دائیں اور ریاضی کے شفٹ دائیں کے درمیان فرق کرنا چاہئے۔ اس سوال کا خیال دراصل صحیح شفٹ سے صفر کرنا ہے۔ یہاں گے 1<<(y+1) | دو کے بطور تحریری 1< جب اتفاقیہ کو روکنا ہے جب n = 0۔
/* * logicalShift - shift x to the right by n, using a logical shift * Can assume that 0 <= n <= 31 * Examples: logicalShift(0x87654321,4) = 0x08765432 * Legal ops: ! ~ & ^ | + <> * Max ops: 20 * Rating: 3 */ int logicalShift(int x, int n) { int y = 32 + (~n)//31-n return (x >> n) & ((1 << y) + (~0) + (1 << y)) }
  1. بٹکاونٹ
    اس عنوان کے ل I ، میں صرف لوپنگ کے متشدد طریقہ اور اس کا اطلاق جانتا ہوں x&(x-1) ، میں نے انٹرنیٹ پر کچھ دوسرے طریقوں کو دیکھا۔
    صرف کوڈ پوسٹ کریں اور شاید اسے سمجھ نہیں سکتے ہیں۔ پانچ مستقل اجزاء 0x55555555 ، 0x33333333 ، 0x0f0f0f0f ، 0x00ff00ff ، 0x0000ffff یہاں استعمال کیے جاتے ہیں ، اور 5 ہندسے بائنری میں لکھے جاتے ہیں ، جو 1 0، 2 0، 4 0، 8 0، اور 16 0 ہیں۔
    وقفہ 1 ، 2 ، 4 ، 8 ، 16 بار کے مطابق دائیں شفٹ کا حساب لگائیں۔
    تقسیم اور فتح کے خیال سے ملتا جلتا ہے۔
/* * bitCount - returns count of number of 1's in word * Examples: bitCount(5) = 2, bitCount(7) = 3 * Legal ops: ! ~ & ^ | + <> * Max ops: 40 * Rating: 4 */ int bitCount(int x) (_mask3<<16) int mask4 = (0xff)
  1. بینگ
    یہ سوال مختلف نتائج حاصل کرنے کے لئے 0 اور غیر صفر کو تقسیم کرنا ہے۔ لہذا استعمال کرنے کے لئے 0 کی ایک خاص پراپرٹی یہ ہے کہ 0 کے برعکس اب بھی خود ہے۔ مخالف نمبروں کی نمائندگی ~x+1
/* * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + <> * Max ops: 12 * Rating: 4 */ int bang(int x) ~x + 1) >> 31) + 1
  1. tmin
    ذیلی سوالات بھیجیں
/* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + <> * Max ops: 4 * Rating: 1 */ int tmin(void) { return 1 << 31 }
  1. فٹ بیٹس
    ایکس کو دائیں طرف n-1 مقامات کے ذریعہ شفٹ کریں ، اور فیصلہ کریں کہ باقی تعداد تمام 1s یا تمام 0s ہے۔ اگر شرائط پوری ہوجائیں تو ، دائیں شفٹ کے بعد ایک x اور x + 1 میں 0 ہونا ضروری ہے۔
/* * fitsBits - return 1 if x can be represented as an * n-bit, two's complement integer. * 1 <= n <= 32 * Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1 * Legal ops: ! ~ & ^ | + <> * Max ops: 15 * Rating: 2 */ int fitsBits(int x, int n) x >>= ~(~n + 1) return (!x
  1. divpwr2
    ڈویژن 0 کے ذریعہ گول ہے۔ لیکن اس شفٹ کا عمل بالکل نیچے ہے۔ لہذا جب ایکس منفی ہے تو ، آفسیٹ ویلیو (1<((x>>31)&1< شامل کریں صرف اس صورت میں جب ایکس منفی ہے تو ایک درست قدر ہوسکتی ہے۔
/* * divpwr2 - Compute x/(2^n), for 0 <= n <= 30 * Round toward zero * Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 * Legal ops: ! ~ & ^ | + <> * Max ops: 15 * Rating: 2 */ int divpwr2(int x, int n) { return (x+(((x>>31)&1)<<n)+(~0)+(!((x>>31)&1)))>>n }
  1. نفی کرنا
    بنیادی علم.
/* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + <> * Max ops: 5 * Rating: 2 */ int negate(int x) { return ~x+1 }
  1. isPositive
    دیکھنے کے ل it یہ منفی ہے یا 0
/* * isPositive - return 1 if x > 0, return 0 otherwise * Example: isPositive(-1) = 0. * Legal ops: ! ~ & ^ | + <> * Max ops: 8 * Rating: 3 */ int isPositive(int x) return !((x >> 31 & 1)
  1. isLessOrEqual
    جج y-x | مثبت اور منفی ، لیکن اوور فلو کے مسئلے پر توجہ دیں۔ اگر یہ مخالف علامت ہے تو ، اتنا بہاو آسان ہے۔ لہذا ، براہ راست غلطی کے بجائے خصوصی فیصلہ کرنا ضروری ہے۔
/* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + <> * Max ops: 24 * Rating: 3 */ int isLessOrEqual(int x, int y) ((!isSameSign) & signx) return ans
  1. دریائے 2
    خیال: ایکس بائنری میں سب سے زیادہ 1 تلاش کریں۔
    فارمولہ: log2 (x) = 16 × a + 8 × b + 4 × c + 2 × d + 1 × e.
    دائیں 16 بٹس میں شفٹ کریں ، فیصلہ کریں کہ آیا یہ 0 ہے ، یہ a کی قدر ہے ، جاننے کے بعد ، شفٹ (8 + 16 × a) بٹس دائیں ، فیصلہ کریں کہ آیا یہ 0 ہے ، اور بی کی قدر حاصل کریں…
/* * ilog2 - return floor(log base 2 of x), where x > 0 * Example: ilog2(16) = 4 * Legal ops: ! ~ & ^ | + <> * Max ops: 90 * Rating: 4 */ int ilog2(int x) { int ans = 0 ans = ans + ((!!(x>>(16 + ans)))<<4) ans = ans + ((!!(x>>(8 + ans)))<<3) ans = ans + ((!!(x>>(4 + ans)))<<2) ans = ans + ((!!(x>>(2 + ans)))<<1) ans = ans + ((!!(x>>(1 + ans)))<<0) return ans }
  1. فلوٹ_نیگ
    سائن بٹ کو الٹ دیں ، این این کے خصوصی معاملے پر توجہ دیں۔
/* * float_neg - Return bit-level equivalent of expression -f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representations of * single-precision floating point values. * When argument is NaN, return argument. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 10 * Rating: 2 */ unsigned float_neg(unsigned uf) { unsigned tmp = uf&(0x7fffffff) unsigned result = uf^(0x80000000) if(tmp>0x7f800000) result=uf return result }
  1. فلوٹ_ i2f
    فلوٹنگ پوائنٹ نمبر سائن بٹ ، آرڈر کوڈ اور اعشاریہ حصہ پر مشتمل ہے۔ گول حص partہ پر خصوصی توجہ دیں: عدد عدد گول۔ استعمال (f > 128) || ((f == 128) && (tail & 1)) نمائندگی کرنا (f چھوٹا ہوا حصہ ہے)
/* * float_i2f - Return bit-level equivalent of expression (float) x * Result is returned as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point values. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, whilef * Max ops: 30 * Rating: 4 */ unsigned float_i2f(int x) { unsigned ans int tmpx = x int f = 0 int delta = 0 int tail = 0 int E = 0 //Special case if (x == 0) return x if (x == 0x80000000) return 0xcf000000 //Sign bit ans = x & 0x80000000 //Take the absolute value if (ans) tmpx = -x //Calculate the number of shifts while ((tmpx >> E)) E++ E = E - 1 //Shift tmpx = tmpx << (31 - E) //The mantissa is truncated to eight digits tail = (tmpx >> 8) & 0x007FFFFF //Cut off part f = tmpx & 0xff //The case of rounding up delta = (f > 128) || ((f == 128) && (tail & 1)) tail += delta //Order code calculation E = E + 127 //Overflow judgment if (tail >> 23) { tail = tail & 0x007FFFFF E += 1 } ans = ans | E << 23 | tail return ans }
  1. float_twice
    پہلے یہ طے کریں کہ انف اور این این خود کو واپس کردیئے گئے ہیں۔ ڈینورملائزیشن مانٹیسا کے حصے کو تھوڑا سا بائیں طرف منتقل کرتا ہے ، اور عام کرنے کے آرڈر کوڈ میں 1 اضافہ ہوتا ہے ، لیکن اس صورتحال پر توجہ دیں کہ یہ لامحدود ہوجاتا ہے۔
/* * float_twice - Return bit-level equivalent of expression 2*f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * When argument is NaN, return argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_twice(unsigned uf) { unsigned sign = uf >> 31 unsigned exp = uf >> 23 & 0xFF unsigned frac = uf & 0x7FFFFF if (exp == 0 && frac < 0x7FFFFF) frac <<= 1 else if (exp == 0 && frac == 0x7FFFFF) { exp += 1 frac = 0x7FFFFE } //Denormalized else if (exp == 0xFE) { exp = 0xFF frac = 0 } else if (exp == 0xFF) return uf else exp += 1 return (sign << 31) | (exp << 23) | frac }

آپریشن کا نتیجہ:

خلاصہ:
میرے خیال میں سب سے مشکل چیزیں بٹ کاؤنٹی ، آئلوگ 2 ، فلوٹ_ آئ 2 ایف اور فلوٹ_ٹائس ہیں۔ مجھے لگتا ہے کہ میں نے صرف بنیادی معلومات کے ایک حصے میں مہارت حاصل کی ہے اور میں لچکدار استعمال سے واقف نہیں ہوں۔ تیرتے ہوئے نمبروں کی حد کے حالات ، آپریشنوں کا اتپرواہ ، چکر لگانے کا علم اور دوسروں کی ہوشیار سوچ سبھی اس سے سیکھا جاسکتا ہے۔