# CSAPP DataLab 题解

Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

# DataLab

## bitXor

`/*  * bitXor - x^y using only ~ and &  *   Example: bitXor(4, 5) = 1 *   Legal ops: ~ & *   Max ops: 14 *   Rating: 1 */int bitXor(int x, int y) {  return ~(~(x & ~y) & ~(~x & y));}`

`/*  * tmin - return minimum two's complement integer  *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 4 *   Rating: 1 */int tmin(void) {  return 1 << 31;}`

## isTmax

`/* * isTmax - returns 1 if x is the maximum, two's complement number, *     and 0 otherwise  *   Legal ops: ! ~ & ^ | + *   Max ops: 10 *   Rating: 1 */int isTmax(int x) {  return !(~(1 << 31) ^ x);}`

`int isTmax(int x) {  return !(~((x + 1) + x) | !(x + 1));}`

## allOddBits

`/*  * allOddBits - return 1 if all odd-numbered bits in word set to 1 *   where bits are numbered from 0 (least significant) to 31 (most significant) *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 12 *   Rating: 2 */int allOddBits(int x) {  int odd = (0xAA << 24) + (0xAA << 16) + (0xAA << 8) + 0xAA;  return !((x & odd) ^ odd);}`

## negate

`/*  * negate - return -x  *   Example: negate(1) = -1. *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 5 *   Rating: 2 */int negate(int x) {  return ~x + 1;}`

## isAsciiDigit

`/*  * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9') *   Example: isAsciiDigit(0x35) = 1. *            isAsciiDigit(0x3a) = 0. *            isAsciiDigit(0x05) = 0. *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 15 *   Rating: 3 */int isAsciiDigit(int x) {  /* (x - 0x30 >= 0) && (0x39 - x) >=0 */  int TMIN = 1 << 31;  return !((x + ~0x30 + 1) & TMIN) & !((0x39 + ~x + 1) & TMIN);}`

## conditional

`/*  * conditional - same as x ? y : z  *   Example: conditional(2,4,5) = 4 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 16 *   Rating: 3 */int conditional(int x, int y, int z) {  int f = ~(!x) + 1;  int of = ~f;  return ((f ^ y) & of) | ((of ^ z) & f);}`

## isLessOrEqual

`/*  * 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) {  /* (y >=0 && x <0) || ((x * y >= 0) && (y + (-x) >= 0)) */  int signX = (x >> 31) & 1;  int signY = (y >> 31) & 1;  int signXSubY = ((y + ~x + 1) >> 31) & 1;  return (signX & ~signY) | (!(signX ^ signY) & !signXSubY);}`

## logicalNeg

`/*  * logicalNeg - implement the ! operator, using all of  *              the legal operators except ! *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 *   Legal ops: ~ & ^ | + << >> *   Max ops: 12 *   Rating: 4  */int logicalNeg(int x) {  int sign = (x >> 31) & 1;  int TMAX = ~(1 << 31);  return (sign ^ 1) & ((((x + TMAX) >> 31) & 1) ^ 1);}`

x 小于 0 时结果为 1，否则检查 `x + TMAX` 是否进位为负数。

## howManyBits

`/* howManyBits - return the minimum number of bits required to represent x in *             two's complement *  Examples: howManyBits(12) = 5 *            howManyBits(298) = 10 *            howManyBits(-5) = 4 *            howManyBits(0)  = 1 *            howManyBits(-1) = 1 *            howManyBits(0x80000000) = 32 *  Legal ops: ! ~ & ^ | + << >> *  Max ops: 90 *  Rating: 4 */int howManyBits(int x) {  int sign = (x >> 31) & 1;  int f = ~(!sign) + 1;  int of = ~f;  /*   * NOTing x to remove the effect of the sign bit.   * x = x < 0 ? ~x : x   */  x = ((f ^ ~x) & of) | ((of ^ x) & f);  /*   * We need to get the index of the highest bit 1.   * Easy to find that if it's even-numbered, `n` will lose the length of 1.   * But the odd-numvered won't.   * So let's left shift 1 (for the first 1) to fix this.   */  x |= (x << 1);  int n = 0;  // Get index with bisection.  n += (!!(x & (~0 << (n + 16)))) << 4;  n += (!!(x & (~0 << (n + 8)))) << 3;  n += (!!(x & (~0 << (n + 4)))) << 2;  n += (!!(x & (~0 << (n + 2)))) << 1;  n += !!(x & (~0 << (n + 1)));  // Add one more for the sign bit.  return n + 1;}`

## floatScale2

`/*  * floatScale2 - 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 floatScale2(unsigned uf) {  int exp = (uf >> 23) & 0xFF;  // Special  if (exp == 0xFF)    return uf;  // Denormalized  if (exp == 0)    return ((uf & 0x007fffff) << 1) | (uf & (1 << 31));  // Normalized  return uf + (1 << 23);}`

## floatFloat2Int

`/*  * floatFloat2Int - Return bit-level equivalent of expression (int) f *   for floating point argument f. *   Argument is passed as unsigned int, but *   it is to be interpreted as the bit-level representation of a *   single-precision floating point value. *   Anything out of range (including NaN and infinity) should return *   0x80000000u. *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while *   Max ops: 30 *   Rating: 4 */int floatFloat2Int(unsigned uf) {  int TMIN = 1 << 31;  int exp = ((uf >> 23) & 0xFF) - 127;  // Out of range  if (exp > 31)    return TMIN;  if (exp < 0)    return 0;  int frac = (uf & 0x007fffff) | 0x00800000;  // Left shift or right shift  int f = (exp > 23) ? (frac << (exp - 23)) : (frac >> (23 - exp));  // Sign  return (uf & TMIN) ? -f : f;}`

## floatPower2

`/*  * floatPower2 - Return bit-level equivalent of the expression 2.0^x *   (2.0 raised to the power x) for any 32-bit integer x. * *   The unsigned value that is returned should have the identical bit *   representation as the single-precision floating-point number 2.0^x. *   If the result is too small to be represented as a denorm, return *   0. If too large, return +INF. *  *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while  *   Max ops: 30  *   Rating: 4 */unsigned floatPower2(int x) {  int exp = x + 127;  // 0  if (exp <= 0)    return 0;  // INF  if (exp >= 0xFF)    return 0x7f800000;  return exp << 23;}`