You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting if the shift amount
is less than 0 or greater than 31.
Part1：整数
1.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 2;
}
思路1（利用小结论）：
-
已知的结论有：
x ^ y = (~x & y) | (x & ~y) -
但是题目中不能使用
|，所以要将|转化为~和&，而又有结论x | y = ~ (~x & ~y)
因此综合上面的两点可以写出版本一：
int bitXor(int x, int y) {
return ~(~(~x & y) & ~(x & ~y));
}
思路2（直接推导）：
因此版本2：
int bitXor(int x, int y) {
return ~(x & y) & ~(~x & ~y);
}
2.tmin
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 2;
}
思路：tmin的16进制形式为0x80000000，写出即可
代码如下：
int tmin(void) {
return 1 << 32;
}
3.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 2;
}
思路：
-
TMax具有如下性质：
（x+1）== ~x（这个称为条件1） -
但是对于
-1（0xffffffff）也具有上面的性质，因此要加上条件2 —x+1不为0 -
条件1：
（x+1）== ~x可以用legal ops表述为!((x+1) ^ (~x))
综合上面的条件可得如下代码：
int isTmax(int x) {
int flag1 = (x + 1) ^ (~x);
int flag2 = (x + 1);
return !(flag1 | !flag2);
}
4.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) {
return 2;
}
思路：
较为简单，与0xAAAAAAAA与运算之后得到0xAAAAAAAA即为满足条件
由课后习题2.15可知：x==y可以通过位运算!(x ^y)实现
因此代码如下：
int allOddBits(int x) {
int oddnumber = (0xAA<<24) + (0xAA<<16) + (0xAA<<8) + 0xAA;
return !((x & oddnumber) ^ oddnumber);
}
5.Negate
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
int negate(int x) {
return 2;
}
思路：
很简单的结论：
int negate(int x) {
return (~x + 1);
}
6.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) {
return 2;
}
思路：
要满足0x30 <= x <= 0x39可以拆解为以下两个条件：
- x的高28位和0x30完全相同，这个可以通过
！(x >> 4) ^ 3实现 - x的低4位位于0到9之间，换一种说法，取出x的低四位再加6一定不会进位
分析即可得到的最后结果如下：
int isAsciiDigit(int x) {
int flag1 = (x >> 4) ^ 3;
int flag2 = ((x & 0xF) + 6) >> 4;
return !(flag1 | flag2);
}
7.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 2;
}
思路：
关键在于使用！来化整并且将x=0和x!=0转化为0x00000000和0xFFFFFFFF
-
当
x=0时，!!x = 0，考虑~(!!x) + 1 = 0x00000000 -
当
x!=0时，!!x = 1，考虑~(!!x) + 1 = 0xFFFFFFFF -
最后分别用
x与~x和yz作与运算即可
int conditional(int x, int y, int z) {
x = ~(!!x) + 1;
return (~x & z) + (x & y);
}
8.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;
}
思路：
其实这道题的关键在于因为溢出现象的存在我们没办法只使用符号位来判断y - x的正负，那就有办法啦，可以分类讨论嘛
-
x y同号
这时候并不溢出，直接用
y + ~x + 1的符号位判断即可 -
x y异号
这个时候要满足x <= y一定是x为负而y非负
思路理清了之后就很容易写出下面的代码：
int isLessOrEqual(int x, int y) {
int signx = (x >> 31) & 1;
int signy = (y >> 31) & 1;
int flag1 = signx ^ signy;
int flag2 = (y + ~x + 1) >> 31;
return (!flag1 & !flag2) | (flag1 & signx);
}
9.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) {
return 2;
}
思路：
x 与 -x做或运算之后符号位仍然为零的只有0
x=0时((~ x + 1) | x) >> 31得到0x00000000，加1就是1x!=0时由于算术右移((~ x + 1) | x) >> 31得到0xFFFFFFFF，加1溢出就是0
代码如下：
int logicalNeg(int x) {
return (((~ x + 1) | x) >> 31) + 1;
}
10.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) {
return 2;
}
思路：
没做出来，只能尽量清楚地将思路阐述出来
第一步是统一正负数和0的处理：
- 当x为正数时需要找到最高位的1，除此之外还需要加上一位0作符号位
- 当x为0时也适用于上面的做法
- 当x为负数时，需要找到最高位的0，除此之外还需要加上一位1作符号位，为了统一与非负数的处理，对负数取反即可遵循上面的处理得到同样正确的结果
主要思想是二分法:
step1：处理32位数
先判断高16位是否有1，如果有1则变量b16为16，没有则变量b16为0
右移b16位
- 如果高16位有1相当于我们处理过低16位了只需处理高16位
- 如果高16位没1相当于只需要处理低16位
step2：处理16位数
对处理后的x判断高8位是否有1，如果有1则变量b8为8，没有则变量b8为0
右移b8位
- 如果高8位有1相当于我们处理过低8位了只需处理高8位
- 如果高8位没1相当于只需要处理低8位
step3：处理8位数
对处理后的x判断高4位是否有1，如果有1则变量b4为4，没有则变量b4为0
右移b4位
- 如果高4位有1相当于我们处理过低4位了只需处理高4位
- 如果高4位没1相当于只需要处理低4位
step4：处理4位数
对处理后的x判断高2位是否有1，如果有1则变量b2为2，没有则变量b4为0
右移b2位
- 如果高2位有1相当于我们处理过低2位了只需处理高2位
- 如果高2位没1相当于只需要处理低2位
step5：处理2位数
对处理后的x判断高1位是否有1，如果有1则变量b1为1，没有则变量b1为0
右移b1位
- 如果高1位有1相当于我们处理过低1位了只需处理高1位
- 如果高1位没1相当于只需要处理低1位
step6：处理1位数
这时x=0or1，直接赋给b0即可
最后得到的结果为b16 + b8 + b4 + b2 + b1 + b0 + 1
int howManyBits(int x) {
int b16, b8, b4, b2, b1, b0;
int flag = x >> 31;
x = (~flag & x) | ((flag & ~x));
b16 = (!!(x >> 16)) << 4;
x = x >> b16;
b8 = (!!(x >> 8)) << 3;
x = x >> b8;
b4 = (!!(x >> 4)) << 2;
x = x >> b4;
b2 = (!!(x >> 2)) << 1;
x = x >> b2;
b1 = (!!(x >> 1)) << 0;
x = x >> b1;
b0 = x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}
Part2：浮点数
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) {
return 2;
}
思路：
32字节的数来表示浮点数的话第一位s，接下来八位表示exp可转化为阶码，最后23位表示小数位可转化为尾数
因此所有题目第一步先将他们取出来
- unsigned sign = (uf >> 31) & 0x1;
- unsigned exp = (uf >> 23) & 0xFF;
- unsigned frac = uf & 0x7FFFFF;
然后分为三类：
1.非规格化值（exp==0x00）
这个时候乘2只需要让frac往左移动一位即可（当frac最高位为1时可以让浮点数由非规格化值转化到规格化的值）
2.特殊值（exp == 0xFF）
这个返回自己即可
3.规格化值
这个时候乘2只需要让exp+1即可（当exp==0xFD时可以让浮点数由规格化值转化到特殊值）
代码如下：
unsigned floatScale2(unsigned uf) {
unsigned sign = (uf >> 31) & 0x1;
unsigned exp = (uf >> 23) & 0xFF;
unsigned frac = uf & 0x7FFFFF;
if (exp == 0xFF) return uf;
else if (exp == 0x00) frac <<= 1;
else exp++;
return (sign << 31) | (exp << 23) | frac;
}
2.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) {
return 2;
}
思路：
第一步还是取出s exp frac，并根据偏置计算出阶码和尾数
列出下表：
| format（32字节） | 最小值 | 最大值 |
|---|---|---|
| 非规格化数 | 2 − 149 2^{-149} 2−149 | 2 − 126 ( 1 − ϵ ) 2^{-126}(1-\epsilon) 2−126(1−ϵ) |
| 规格化数 | 2 − 126 2^{-126} 2−126 | 2 127 ( 2 − ϵ ) 2^{127}(2-\epsilon) 2127(2−ϵ) |
这个题有很多种可能性可以合并，但因为不是太熟练，所以我就严格按照非规格化值、特殊值、规格化值一一分类，这样也是可以通过的
-
非规格化值（exp==0x00）
此时绝对值小于1，无论正负向0舍入，返回0
-
特殊值（exp == 0xff）
溢出，返回0x80000000u
-
规格化值
先不考虑符号位，最后再转化
-
E < 0此时绝对值小于1，返回0
-
E >= 31，此时超过int能表示的范围，溢出
-
E < 23，M末尾的 (23 - E) 个数被舍入
-
23 <= E < 31 需要在M的最后加上frac 的末尾添加 (E - 23) 个 0
-
当x为负数时进行一步从x到~x+1的转化即可
代码如下：
int floatFloat2Int(unsigned uf) {
unsigned sign = (uf >> 31) & 0x1;
unsigned bias = (1 << 7) - 1;
unsigned exp = (uf >> 23) & 0xFF;
unsigned frac = uf & 0x7FFFFF;
int E = exp - bias;
int M = frac | (1 << 23);
if (exp == 0) {
return 0;
} else if (exp == 0xff) {
return 0x80000000u;
} else {
if (E < 0) return 0;
else if (E >= 31) return 0x80000000u;
else if (E < 23) M >>= (23 - E);
else M <<= (E - 23);
}
return (sign ? (~M + 1) : M);
}
3.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) {
return 2;
}
思路：
| format（32字节） | 最小值 | 最大值 |
|---|---|---|
| 非规格化数 | 2 − 149 2^{-149} 2−149 | 2 − 126 ( 1 − ϵ ) 2^{-126}(1-\epsilon) 2−126(1−ϵ) |
| 规格化数 | 2 − 126 2^{-126} 2−126 | 2 127 ( 2 − ϵ ) 2^{127}(2-\epsilon) 2127(2−ϵ) |
利用下面的表格很容易分析如下：
- 当x < -149时超出表示范围，返回0
- 当x > 127时过大超出表示范围，返回(0xFF) << 23
- 当-149 <= x < -126时用非规格数表示，1 << (x + 149)
- 当-126 <= x <= 127时用规格数表示，(x + 127) << 23
可以写出下面的代码：
unsigned floatPower2(int x) {
if (x < -149) return 0;
else if (x < -126) return 1 << (x + 149);
else if (x <= 127) return (x + 127) << 23;
else return (0xFF) << 23;
}
