[toc]
概 述
通过禁止你使用if else || && 等等操作，锻炼你使用 位运算 的能力。
一定要去分析每道题的数值特点，比如 isTmax，你要思考 Tmax 有什么特殊的地方
这篇内容只是提供了一种可能的答案，如果你只是看而不自己做，那么完全不会有任何收获
友情提示，一定要写注释！否则你就会像我一样，写博客的时候，完全不知道自己之前写了个啥
温馨提示，如果做题过程中做到怀疑自己的智商，不要气馁！因为俺也一样！我第一次做这个lab，用了7个小时，还是有4道不会做。如果从头到尾没有怀疑过自己，那么恭喜你，你就是大佬！
位异或 bitXor
- 题目
//1
/*
* 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;
}
- 思路
异或，相同为0，相异为1。相同的话，不是11就是00。
x & y;就是找出11，(~x) & (~y);就是找出00。
那么正确答案就是，既不是11，也不是00，也就是下方的代码实现。
- 代码实现
int bitXor(int x, int y) {
int a = x & y;
int b = (~x) & (~y);
int res = (~a) & (~b);
return res;
}
Tmin
- 题目
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
}
- 思路
Tmin就是最小的那个负数值，比较特殊，因为没有和它互为相反的正值。
补码是 0x80000000， 所以直接对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
*/
// Tmax + 1等于Tmin， Tmax ~ 也等于 Tmin
int isTmax(int x) {
}
- 思路
因为最后的答案要输出 1 或者 0，所以最外层的符号一定是 !
而且 ！内部一定要区分为 0 或者 非0
答案的形式观察好了，就可以分析下 Tmax 了，这个数有两个特性：
- Tmax + 1 == Tmin
- ~Tmax == Tmin
把这两个特性写下来，然后通过 位与& 来生成 0 或者 非0。最外层加个 ！ 就完事了
int isTmax(int x) {
return !((~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
*/
// 所有的奇数bit都是1
int allOddBits(int x) {
}
- 思路
和上一题一样的路数，最后输出1，那么外层是 ！
那么我们只要把标准的所有奇数都是1的二进制写出来就行了，它是 0xAAAAAAAA。
让输入x 和 0xAAAAAAAA 位与，就采集了所有的奇数位，再和 0xAAAAAAAA 位异或^，
如果为0就说明，所有的奇数位都是 1
int allOddBits(int x) {
int a = 0xAA + (0xAA << 8);
int b = a + (a << 16); // b == 0xAAAAAAAA
return !((b & x) ^ b);
}
negate
- 题目
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
}
- 思路
没啥好说的，相反数的公式就是 ~x + 1
顺便提一下， 有两个数的相反数是它本身，第一个是 0， 第二个是 Tmin
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， 最高位为 0， 减去0x3A应该小于0，最高位为 1.
所以 & Tmax， 只保留最高位，然后如果结果 为 0， 那么 非！后就变成1了， 应该为1， ！！ 就变成1 了，
最后两个 0x1 0x1 位与， 得到1， 如果其中一边为 0，就说明不满足，最后输出0
int isAsciiDigit(int x) {
int Tmin = 1 << 31;
int a = x + (~0x30 + 1); // 做减法
int b = x + (~0x3A + 1);
int res = (!(a & Tmin)) & (!!(b & Tmin));
return res;
}
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) {
}
- 思路
return y + z 的组合，当然要对y，z 乘以一些东西，使得 有 y 没 z， 反之亦然
所以我相中了 -1，因为-1是全1，所以 & y 肯定等于 y 本身， 而且 -1 + 1 == 0。
如果 x == 1，！x == 0，那么y会保留， z 的参数就是一个取反，！x == 0 的时候 取反等于 -1 ，再加1等于0， z 消失
也就是说，如果！x == 1，（-1 + 1 == 0）那么y就会消失，z会保留. 因为 ~(1) + 1 == -1 ，也就是 0xFFFFFFFF，&z 保留z
int conditional(int x, int y, int z) {
int minus_1 = ~(0);
return (minus_1 + !x) & y + (~(!x) + 1) & z;
}
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) {
return 2;
}
- 思路
判断符号位，如果 x == y ，那么返回1， 然后判断 x < y 最后形式应该是 两个东西被 位或 | 连接
后面就是 x - y 判断一下 符号位是不是1，是 1 就成立， 不是 就应该为 0
int isLessOrEqual(int x, int y) {
int a = (!(x ^ y)); // x ==y a == 1, x != y ,a == 0
int b = x + ~(y) + 1; // x - y
int Tmin = 1 << 31;
return a | !!(b & Tmin);
}
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) {
}
- 思路
这种时候就得想想， 0 的特点是什么， 0的相反数， 还是0 啊， 符号相同，
但是一定别忘了 特例， Tmin, 这玩意也相同，所以 要 判断是是不是 Tmin
感觉是脑子僵住了，明明已经想到了对策，但是实在是太乱了脑袋，所以突然就不会做了。
实在是特么的不会了，看的答案， ~(b) & ~(c) 可以保证， 只有 0 才能 让 最高位 为 1， 然后右移， & 1 ，就行了，
总结一下，因为以前所有的返回1 或者 0，我都是用 ！ 操作的，结果这回没有 ！了，反而有点不会操作了
int logicalNeg(int x) {
int Tmin = 1 << 31;
int b = (~(x) + 1);
int c = x;
return (( ~(b) & (~(c))) >> 31) & 1;
}
howManyBits
下面这几个实在是做不动了，而且感觉根本用不上 float这种类型，基本上业务都是int类型，所以就先不做了。
