コンピューターシステム

コンピュータシステムCSAPPの深い理解：DATALABノート



Deep Understanding Computer System Csapp



目次

内容は、整数と浮動小数点数のビットレベルの演算です。

  1. bitAnd
    ドモルガンの法則を使用します。
/* * 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
    最初にxを右に移動し、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) 2として記述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. bitCount
    このトピックについては、ループの暴力的な方法と適用しか知りませんx&(x-1)、インターネット上で他のいくつかの慣行を見ました。
    コードを投稿するだけで、理解できない場合があります。ここでは、5つの定数0x55555555、0x33333333、0x0f0f0f0f、0x00ff00ff、0x0000ffffが使用され、5桁は、1 0、2 0、4 0、8 0、および160の2進数で書き出されます。
    間隔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. fitsBits
    xをn-1桁右にシフトし、残りの数値がすべて1であるかすべて0であるかを判断します。条件が満たされている場合、右シフト後の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で四捨五入されます。ただし、シフト演算は切り捨てられます。したがって、xが負の場合は、オフセット値を追加します(1<。((x>>31)&1< xが負の場合にのみ、有効な値が存在します。
/* * 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
    負か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. river2
    アイデア：xバイナリで最も高い1を見つけます。
    式：log2（x）= 16×a + 8×b + 4×c + 2×d + 1×e。
    16ビット右にシフトし、0かどうかを判断します。これはaの値です。aを知った後、（8 + 16×a）ビットを右にシフトし、0かどうかを判断し、bの値を取得します…
/* * 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
    符号ビットを反転し、NaNの特殊なケースに注意してください。
/* * 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. float_i2f
    浮動小数点数は、符号ビット、注文コード、および小数部で構成されます。丸め部分には特に注意してください。偶数に丸めます。使用(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
    まず、infとNaNがそれ自体に返されることを確認します。非正規化により仮数部が1ビット左にシフトし、正規化順序コードが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 }

演算結果：

総括する：
最も難しいのはbitCount、ilog2、float_i2f、float_twiceだと思います。基礎知識の一部しか習得しておらず、柔軟な使い方に慣れていない気がします。浮動小数点数の境界条件、演算のオーバーフロー、丸めの知識、および他の人の巧妙な思考はすべて、そこから学ぶことができます。