CSAPP datalab

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

这题是实现按位异或运算，我们由数电知识可以知道

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

Tmin即符号位为1，其余全0的有符号数，直接位运算即可

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

这题我的想法可能和别人的不同，我的想法是，如果x为最大值，那么加一后再按位取反肯定得到的是原来的数(这点很容易想到)，但是在运行时发现有个样例没有考虑到，也就是-1，因为他是全1，所以会有负溢出，然后按位取反后也是-1，所以要将这个单独提出来。对于其他的数，我们很容易的想到加一后不会溢出(每一位都会进位只有特殊情况)，所以我们只需要再判断一下符号位是否为1即可

/*
 * 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
 */

这题我们这样想，首先如果它的奇数位全都是1的话，那么它与最小的满足条件的数按位与后，得到的就是数的奇数位，然后再与最小的满足条件的数按位异或即可，如果全0，表示满足条件，否则不满足条件。

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

按位取反加一即可(这个都会吧)

/*
 * 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
 */

这题我想的稍许复杂，我用的是一项一项排除法，首先排除0x30这两位前面还有数的数，也就是按位异或0x30后判断(x >> 4)是否为0即可。如果满足条件，那么我们就判断后四位，0~9的话只有8，9两个数字第四位为1，所以单独列出来。如果第四位为1，那么我们判断第三位和第二位必须为0，如果第四位为0，直接满足即可。

/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */

这题一直都想着是中间有个|然后做，但是一直没做出来，最后发现自己傻逼了。
对于0，它的按位异或后+1等于全0；对于1，它的按位异或后+1等于全1，所以就考虑两种情况即可。

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */

我想的是，x <= y其实就是 x + (-y) <= 0，然后 -y = ~y + 1，之后排除符号位为1即可。

/*
 * 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
 */

首先排除负数，很简单。然后排除正数，通过正溢出来选出0，因为只有~0 + 1 = Tmin，其他的正数都不可能得到Tmin

/* 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
 */

这个题，用的是二分，首先判断16位够不够，即左移16位看看是否为0，然后判断8位够不够…以此类推，最后我们就可以得到答案。在这里有个小细节，就是最后只剩一位的时候，我们左移一位，发现为0，也就不累加，所以我们最后还是要把x加上去。

//float
/*
 * 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
 */

首先题目说了当参数为NaN的时候直接返回参数，当然如果参数为无穷的时候我们也返回无穷，所以这两种情况是一样的，即指数位全为1的时候返回参数即可。如果不全为1，我们只需要判断一下指数位是否全0，全0的话我们只需要将数右移一位即可，如果不全0，我们将指数位+1即可。

/*
 * 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
 */

首先，我们知道小于0的float值强制转换为int的话为0，也就是指数位小于127(加上偏置值小于0)的。如果此时指数位大于等于31 + 127 = 158的话，那么就代表我们要表示的数为$(2-\epsilon )\ast 2^{31}$，而int不能表示大于$2^{31}-1$的数，所以此时我们返回0x80000000u即可。
其次，我们想着如何把一个整数放到float，我们先化为科学计算，然后将小数点后面的数移到23位里面做舍入操作…所以逆过程其实就是把23位小数位拿出来，然后添上1，然后根据指数位的大小来决定左移还是右移。因为此时我们默认小数点在最后，此时我们需要将那个指数为减去127和23来确定左移还是右移。

/*
 * 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
 */

首先我们可以知道$2^x=1.0\ast 2^x$
我们首先将x加上127偏置值，如果此时大于等于255，表示无穷大，如果小于-22，我们直接返回0，因为这个时候非规格数都不能表达，能用非规格数表达的数的范围是$2^{-23-126}$~$(1-\epsilon )2^{-126}$即$1.x\times 2^{-127}$，所以用非规格的话可以表示$2^{-127}$，然后我们只需要将1右移22+x位即可。规格数直接右移23位
此题可以贴一下代码:

unsigned floatPower2(int x) {
    x = x + 127;
    if (x >= 255) {
        return 0xff << 23;
    }
    if (x < -22) {
        return 0;
    }
    if (x >= -22 && x < 1) {
        return 1 << (22 + x);
    }
    return x << 23;
}