此为在课程学习中布置的datalab，相对于官网提供的版本是有所修改的，因此题目和官网的版本并不是一致的。但总体上来说大同小异，毕竟重要的不是题目，而是思想。 这样的训练的主要目的是加深对系统的各种理解。因为感觉如果直接写完就扔掉不管的话，就会很快就忘记各种思路，使得训练达不到应有的效果，所以决定在上记录自己的思路，以加深印象，同时，如果可能的话，也希望能给后来人提供一些思路上的指引。
通过练习，熟练位操作级别的运算与二补数的性质。
函数实现：
/* NO: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) { return ~((~x) | (~y)); }函数分析：
如图1-1所示，与门可以拆分为非门和或门的组合：
图1-1而按位运算无非是分别对每一位进行运算，因此也可以像图1-1一样进行分解，分解为三个按位非和一个按位或
函数实现：
/* NO:2 * bitNor - ~(x|y) using only ~ and & * Example: bitNor(0x6, 0x5) = 0xFFFFFFF8 * Legal ops: ~ & * Max ops: 8 * Rating: 1 */ int bitNor(int x, int y) { return ~~((~x) & (~y)); }函数分析：
如图2-1所示，或门可以拆分成非门和与门的组合：
图2-1与1一样，按位或可以分解为三个按位非和一个按位与
函数实现：
/* NO:3 * copyLSB - set all bits of result to least significant bit of x * Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000 * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int copyLSB(int x) { return x << 31 >> 31; }函数分析：
int型变量的移位是算术移位，而算术右移的特性是：在空出的高位补上原有的最高位的值。因此，只要将最低位移动到最高位，再将其右移，移回到最低位即可
函数实现：
/* NO:4 * evenBits - return word with all even-numbered bits set to 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 8 * Rating: 2 */ int evenBits(void) { int a = 0x55; return a + (a << 8) + (a << 16) + (a << 24); }函数分析：
最低位为第零位，也是偶数，因此此数满足：01010101…0101的特性。由于每八位都是相等的，并且允许定义0x00-0xff范围内的常数，因此，定义一个常数a=0x55（ 0101010 1 2 01010101_2 010101012），并分别将其左移8位、16位、24位，以完成拼接。
函数实现：
/* NO:5 * logicalShift - shift x to the right by n, using a logical shift * Can assume that 1 <= n <= 31 * Examples: logicalShift(0x87654321,4) = 0x08765432 * Legal ops: ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ int logicalShift(int x, int n) { int firstStep = ((x >> 1) & ~(1 << 31)); return firstStep >> (n + (~1 + 1)); }函数分析：
逻辑移位，关键在于高位补零。因此，如果要将算术移位换为逻辑移位，只需要保证最高位为0即可。 在此处采用的方法是：先右移一位，强行将补上的最高位设置为0，随后再进行剩余次数的移动，这样可以保证此后的算术移位都是补0。 注： ∼ 1 + 1 \sim 1+1 ∼1+1表示 − 1 -1 −1，因为此处不能使用减号，故使用此形式表示相减。
函数实现：
/* NO:6 * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int bang(int x) { int y = ~(~x + 1) & (~x); int z = y >> 31; return (~z) + 1; }函数分析：
此函数的主要目的是将非零的数映射到0，将0映射到1。因此从0的独特之处开始思考：只有0和TMin具有 ∼ x + 1 = x \sim x+1=x ∼x+1=x的特性，这个特性会非常地有用。 分别列出 x = 0 x=0 x=0、 x = T M i n x=TMin x=TMin以及 x x x为其他数时、 ∼ x + 1 \sim x+1 ∼x+1与 x x x的形式：
value x x x ∼ x + 1 \sim x+1 ∼x+1000…0000…00TMin10…0010…00others_pos0*…**1*…**others_neg1*…**0*…**现在的目标是分离出0这个情形——让它与其他三个情形独立开来。最直接的方法就是右移：将所有位全部变为最高位。 如果使用 x & ( ∼ x + 1 ) x\&(\sim x+1) x&(∼x+1)，则会使得只有 x = T M i n x=TMin x=TMin对应的运算结果为11…11，其余的都是00…00。而如果两端取反，使用 ( ∼ x ) & ∼ ( ∼ x + 1 ) (\sim x)\&\sim(\sim x+1) (∼x)&∼(∼x+1)，则会使得只有 x = 0 x=0 x=0对应的运算结果为11…11（对应十进制的-1），其余的都是00…00（对应十进制的0）。这正是想要的情形。 而由于对0取逻辑非的结果为1，对非0取逻辑非的结果为0，则只需将上述对 x = 0 x=0 x=0运算得到的结果-1取负即可（对其他情形下的运算结果0，取负后仍然为0），最后返回目标值。
函数实现：
/* NO:7 * leastBitPos - return a mask that marks the position of the * least significant 1 bit. If x == 0, return 0 * Example: leastBitPos(96) = 0x20 * Legal ops: ! ~ & ^ | + << >> * Max ops: 6 * Rating: 4 */ int leastBitPos(int x) { return x & ((~x) + 1); }函数分析：
设x=…0010…00，其中1后面都是0。 则~x=…1101…11，原来的1变成了0，后面全是1。 因此，~x+1，即-x，等于…1110…00，注意到从原来的1那个位置往后数，还是和之前是一样的，而往前数，则全部反了过来。 此函数的目的是要把1前面的全部数都置0，后面的保留为100…00。因此，使用 x & ( ∼ x + 1 ) x\&(\sim x+1) x&(∼x+1)即可达到目的：最靠后的1保留了下来，其他位全为0。
函数实现：
/* NO:8 * TMax - return maximum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ int tmax(void) { return (1 << 31) + (~1) + 1; }函数分析：
TMax= 0111...111 1 2 0111...1111_2 0111...11112，而TMax+1= 1000...000 0 2 1000...0000_2 1000...00002，因此，只要轻松地得到后者，再减去1就可以得到前者。
函数实现：
/* NO:9 * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int negate(int x) { return (~x) + 1; }函数分析：
根据关系 − x = ∼ x + 1 -x=\sim x+1 −x=∼x+1即可。
函数实现：
/* NO:10 * isPositive - return 1 if x > 0, return 0 otherwise * Example: isPositive(-1) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 8 * Rating: 3 */ int isPositive(int x) { int nonNeg = ((x >> 31) + 1); int zero = (((x + (~1) + 1) >> 31) + 1); return nonNeg & zero; }函数分析：
整体分为两个部分。 第一部分：输入的x是否非负。如果非负，则x>>31必然为0，即：置nonNeg=1。而如果为负，则x>>31必然为-1，即：置nonNeg=0. 第二部分：输入的x与零的关系（此处命名有歧义）。因为要从第一部分中判定为1的集合里，将0抹去，所以此处应该满足：对于输入0，返回0，对于输入正数，返回1。容易注意到，在大于等于0的数中，只有0减去1后会变成负数，因此，对((x-1)>>31)+1进行判定即可（与上述判定类似，只不过这里的x变成了x-1）。 最后，对第一部分（ x ≥ 0 x\ge0 x≥0）和第二部分( x ≠ 0 x\neq 0 x=0)进行与运算即可。
函数实现：
/* NO:11 * isNonNegative - return 1 if x >= 0, return 0 otherwise * Example: isNonNegative(-1) = 0. isNonNegative(0) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 6 * Rating: 3 */ int isNonNegative(int x) { return (x >> 31) + 1; }函数分析：
此函数实现的功能完全与上个函数的第一部分一致，因此可以直接照搬。
函数实现：
/* NO:12 * sum3 - x+y+z using only a single '+' * Example: sum3(3, 4, 5) = 12 * Legal ops: ! ~ & ^ | << >> * Max ops: 16 * Rating: 3 */ /* A helper routine to perform the addition. Don't change this code */ static int sum(int x, int y) { return x+y; } int sum3(int x, int y, int z) { int word1 = 0; int word2 = 0; /************************************************************** Fill in code below that computes values for word1 and word2 without using any '+' operations ***************************************************************/ word1 = x ^ y ^ z; word2 = ((x & y) | (y & z) | (z & x)) << 1; /************************************************************** Don't change anything below here ***************************************************************/ return sum(word1,word2); }函数分析：
首先，对于两个数的加法，a+b： 在不考虑进位的情况下，a+b的每一位应该满足a^b，即：
^01001110现在考虑进位：如果a和b上的某一位都为1，则进一位，进位自然是给左边的那一位加1。由此描述，进位是由(a&b)<<1来表示的。即：a+b=a^b+(a&b)<<1 而对于三个数的加法，a+b+c： 不考虑进位时，容易看出类似于a+b地，a+b+c的每一位应该满足a^b^c。而对于进位，即便a、b、c上的某一位都为1，也只需要给左边进1。因此，不必考虑更复杂的情形，只要a、b、c中至少有两个都为1时，就可以产生进位，且两个为1和三个为1带来的进位都是一样的。 综上所述：a+b+c=a^b^c+((a&b)|(b&c)|(c&a))<<1
函数实现：
/* NO:13 * addOK - Determine if can compute x+y without overflow * Example: addOK(0x80000000,0x80000000) = 0, * addOK(0x80000000,0x70000000) = 1, * Legal ops: ! ~ & ^ | + << >> * Max ops: 20 * Rating: 3 */ int addOK(int x, int y) { int signIdentical = !((x >> 31) ^ (y >> 31)); int signChange = !((((x + y) >> 31) ^ (x >> 31)) + 1); return !(signIdentical & signChange); }函数分析：
int型整数加法溢出时，必然满足： 1、两个加数同号，即符号位相同 2、加法的和与加数异号，即符号位相反 因此，首先使用异或，对两个加数的符号位进行了比较：让符号位填满全部32个bit，如果同号，则异或运算结果为0。反之，异号时，结果为-1。最后取逻辑非，使得同号结果为1，异号结果为0。 随后使用了同样的方法，判断两数的和是否与加数异号，注意在最后取逻辑非之前，使用了+1，使得运算结果变成：同号为0，异号为1。 对上述两个判定结果进行与运算，即可得到是否溢出的判断，最后根据函数的功能要求，再取一次逻辑非，使得溢出时返回0。
函数实现：
/* NO:14 * logicalAbs - absolute value of x (except returns TMin for TMin) * Example: abs(-1) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 10 * Rating: 4 */ int logicalAbs(int x) { int firstStep = (x ^ (x >> 31)); int control = (~(x >> 31)) + 1; return firstStep + control; }函数分析：
取绝对值时，正数应该保持不变，而负数则应该变成相应的正数。 考虑使用异或的关系，让正数运算后不变，负数运算后被取反。发现负数右移31位的结果等于-1（11…11 2 _2 2），而正数右移31位的结果等于0(00…00 2 _2 2)。对于负数而言，移位得到结果在位级别上，全为1，与自身进行按位异或运算时，恰好能够将0变1,1变0。而对于正数而言，则是0和1保持不变。在这样的运算之后，就能够保证正数不变、负数取反。 而负数取反后还要加上1才能真正等于绝对值（正数却不需要），因此要想办法构造一个“区别对待”的、要加上去的数，使得对正数的第一步运算后的结果+0，对负数的第一步运算后的结果+1。注意到正数的 ∼ ( x > > 31 ) + 1 \sim(x>>31)+1 ∼(x>>31)+1结果为0，而负数对应的结果为1。这样一来，就找到了要加上去的数。 因此，将上述两项加在一起返回即可。
函数实现：
/* NO:15 * isNonZero - Check whether x is nonzero using * the legal operators except ! * Examples: isNonZero(3) = 1, isNonZero(0) = 0 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int isNonZero(int x) { int y = ~(~x + 1) & (~x); int z = y >> 31; return z + 1; }函数分析：
此函数的要求，实际上与第6个函数“逻辑非的实现”基本一致，都是区分0和非0的功能。 只不过在此处，要把结果的0与1反过来，之前是将（-1,0）变成（1,0），那么现在只要将（-1,0）变成（0,1）就行了。因此，使用+1的手段即可。
