CSAPP第二章的内容以前组成原理基本都学过…所以就简单翻了翻。
对应的lab是用位运算实现各种有的没的…
题目基本都很tricky…
除了用到一些常规的位运算性质，还用到了一些奇怪的条件:
* ~0x7FFFFFFF = 0x7FFFFFFF + 1
* 0xFFFFFFFF +1 = 0x00000000
*
0 == ~0+1
唯一让我觉得比较有趣的是how many bits这道题
题目要求是给一个32-bit signed int,问最少用多少位能得到它的补码表示。
考虑正数，显然，高位的连续的多个0是不必要的，只需要一个符号位的0即可。
那么对于负数，**高位的连续的多个1也是不必要的。 **原因是，-2^k + 2^(k-1) = -2^(k-1),也就是说，去掉两个连续的1中高位的那个，数值没有改变。
我们可以将正数和负数统一来看，都是找到最高位的0和1的交界。
这可以通过和相邻的位置求异或，找到最高位的1的方式来实现。
接下来就是如何找一个数的最高位的1的位置了。
方法是构造一个单调的函数f,假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.
然后在函数f上二分。
全部问题的代码如下,思路写在注释里了。还有3个涉及浮点数的问题之后补。
1/*
2 * bitXor - x^y using only ~ and &
3 * Example: bitXor(4, 5) = 1
4 * Legal ops: ~ &
5 * Max ops: 14
6 * Rating: 1
7 */
8/* 0 0 -> 0
9 0 1 -> 1
10 1 0 - > 1
11 1 1 - > 0
12*/
13// ~(~a & ~b)&~(a&b)
14int bitXor(int x, int y) {
15 int ans = ~(~x & ~y)&(~(x&y));
16 // printf("%d\n",ans);
17 return ans;
18}
19/*
20 * tmin - return minimum two's complement integer
21 * Legal ops: ! ~ & ^ | + << >>
22 * Max ops: 4
23 * Rating: 1
24 */
25/*
26 0X10000000
27*/
28int tmin(void) {
29
30 int ans = 0x1 << 31;
31 return ans;
32
33
34}
35//2
36/*
37 * isTmax - returns 1 if x is the maximum, two's complement number,
38 * and 0 otherwise
39 * Legal ops: ! ~ & ^ | +
40 * Max ops: 10
41 * Rating: 1
42 * 0x7FFFFFFF
43 */
44int isTmax(int x) {
45 /*
46 大体思路首先是根据，如果x是最大值0x7FFFFFFF,那么~x和x+1(自然溢出)应该相等。
47 不能用等号，但是我们可以用异或。x==y 等价于 !(x^y). 因此有了后半段!(x+1)^(~x)
48 但是满足这个条件的还有-1,也就是0xFFFFFFFF,因此我们需要排除掉-1.
49 还是用异或的性质，这回是0异或者任何数都等于其本身。
50 因此如果x为-1，那么前后两部分都为1，结果为0.
51 如果x为TMAX,那么前面为0，后面为1，结果为1.
52 如果x为其他任何数，前后结果都应为0. 结果为0。
53 */
54 return (!(x+1))^!((x+1)^(~x));
55}
56/*
57 * allOddBits - return 1 if all odd-numbered bits in word set to 1
58 * where bits are numbered from 0 (least significant) to 31 (most significant)
59 * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
60 * Legal ops: ! ~ & ^ | + << >>
61 * Max ops: 12
62 * Rating: 2
63 */
64// 理解错误。误以为是要求当前长度x的所有奇数位上都是1.
65// 实际上要求和x的长度无关，而是要求[0,31]中，所有奇数位上都是1.
66int allOddBits(int x) {
67 int half_mask = (0xAA<<8) | 0xAA;
68 int mask = (half_mask<<16) + half_mask;
69 // printf("mask:X x:x x\n",mask,x,x&mask);
70 return !((x&mask)^mask);
71
72}
73/*
74 * negate - return -x
75 * Example: negate(1) = -1.
76 * Legal ops: ! ~ & ^ | + << >>
77 * Max ops: 5
78 * Rating: 2
79 */
80int negate(int x) {
81 return ~x + 1;
82}
83//3
84/*
85 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
86 * Example: isAsciiDigit(0x35) = 1.
87 * isAsciiDigit(0x3a) = 0.
88 * isAsciiDigit(0x05) = 0.
89 * Legal ops: ! ~ & ^ | + << >>
90 * Max ops: 15
91 * Rating: 3
92 */
93/* 把0-9的二进制写出来，发现0-7占满了3bit的二进制的8种组合。
94 因此考虑只判断8和9两种4bit的情况
95 构造mask,不在意的bit的位置放0，在意的bit位置放1.
96*/
97int isAsciiDigit(int x) {
98 int mask = 0x0E;
99 int ones = x&mask;
100 int ones_3 = ones >> 3;
101 int tens = x>>4;
102 // printf("x: x tens: x ones:x\n",x,tens,ones);
103 int ones_ok = (!(ones^0x8)) | (!ones_3);
104 int tens_ok = !(tens^0x3);
105 return ones_ok & tens_ok;
106
107}
108/*
109 * conditional - same as x ? y : z
110 * Example: conditional(2,4,5) = 4
111 * Legal ops: ! ~ & ^ | + << >>
112 * Max ops: 16
113 * Rating: 3
114 */
115/*
116 关键思路是0xFFFFFFFF和0x00000000之间差了1.
117 而这两个数一个是全部位置都取的mask,一个是全部位置都不取的mask.
118*/
119int conditional(int x, int y, int z) {
120 return z^(!x + ~0 )&(y^z);
121
122}
123/*
124 * isLessOrEqual - if x <= y then return 1, else return 0
125 * Example: isLessOrEqual(4,5) = 1.
126 * Legal ops: ! ~ & ^ | + << >>
127 * Max ops: 24
128 * Rating: 3
129 */
130/*
131 大体思路是，符号位相同和符号位不同分别考虑
132 符号位相同: 考虑差的符号位。
133 符号位不同: 当x<0,y>=0时结果为1.
134*/
135int isLessOrEqual(int x, int y) {
136 int minus = y + (~x+1);
137 int s_x = (x>>31)&1;
138 int s_y = (y>>31)&1;
139 int s_minus = (minus>>31) & 1;
140 return (s_x&(!s_y))| (!(s_x^s_y)&!s_minus);
141}
142//4
143/*
144 * logicalNeg - implement the ! operator, using all of
145 * the legal operators except !
146 * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
147 * Legal ops: ~ & ^ | + << >>
148 * Max ops: 12
149 * Rating: 4
150 */
151/*
152 0 == ~0+1
153 -2147483648 = ~-2147483648+1
154 满足 x == ~x+1
155 重点是x和~x+1的符号位相同，如果都是0那么x=0,如果都是1那么x=-214783648`
156*/
157int logicalNeg(int x) {
158 int s1 = (x>>31)&1;
159 int s2 = ((~x+1)>>31)&1;
160 // printf("s1: %d s2:%d %d %d\n",s1,s2,s1|s2,~(s1|s2));
161 // 1 + negate(0) -> 1
162 // 1 + neagate(1) -> 0
163 return 1+(1+~(s1|s2));
164}
165/* howManyBits - return the minimum number of bits required to represent x in
166 * two's complement
167 * Examples: howManyBits(12) = 5
168 * howManyBits(298) = 10
169 * howManyBits(-5) = 4
170 * howManyBits(0) = 1
171 * howManyBits(-1) = 1 ??? should be 2?
172 * howManyBits(0x80000000) = 32
173 * Legal ops: ! ~ & ^ | + << >>
174 * Max ops: 90
175 * Rating: 4
176 */
177/*
178 思路似乎可以转化成判断一个数（可正可负）的最高位的1的位置。
179 判断最高位1用二分的办法。
180 构造一个单调的函数，假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.
181 被 howManyBits(-1)==1 困扰了好久，实际上就是0x1，只有一位，改位就是符号位的情况。
182*/
183int howManyBits(int x) {
184 int n = 0 ;
185 x^=(x<<1);
186 n += (!!( x & ((~0) << (n + 16)) )) << 4; // 看高16位是否为0，是的话区间为[0,16),否的话为[16,32)
187 // printf("n:%d\n",n);
188 // printf("%d\n",!!(x & ((~0) << (n + 16))));
189 n += (!!( x & ((~0) << (n + 8)) )) << 3;
190 // printf("n:%d\n",n);
191 n += (!!( x & ((~0) << (n + 4)) )) << 2;
192 // printf("n:%d\n",n);
193 n += (!!( x & ((~0) << (n + 2)) )) << 1;
194 // printf("n:%d\n",n);
195 n += (!!( x & ((~0) << (n + 1)) ));
196 // printf("n:%d\n",n);
197
198 // int s = (x>>31)&1;
199 // int ret = n+1+((1^s)&(!!x));
200 // // printf("x:%d ret:%d\n",x,ret);
201
202 return n+1;
203}补上三个涉及浮点数的问题…比较无聊，按照IEEE754操作即可．
1//float
2/*
3 * floatScale2 - Return bit-level equivalent of expression 2*f for
4 * floating point argument f.
5 * Both the argument and result are passed as unsigned int's, but
6 * they are to be interpreted as the bit-level representation of
7 * single-precision floating point values.
8 * When argument is NaN, return argument
9 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
10 * Max ops: 30
11 * Rating: 4
12 */
13unsigned floatScale2(unsigned uf)
14{
15 int exp_ = (uf & 0x7f800000) >> 23;
16 int s_ = uf & 0x80000000;
17 if (exp_ == 0)
18 return (uf << 1) | s_;
19 if (exp_ == 255)
20 return uf;
21 ++exp_;
22 if (exp_ == 255)
23 return 0x7f800000 | s_;
24 return (uf & 0x807fffff) | (exp_ << 23);
25}
26/*
27 * floatFloat2Int - Return bit-level equivalent of expression (int) f
28 * for floating point argument f.
29 * Argument is passed as unsigned int, but
30 * it is to be interpreted as the bit-level representation of a
31 * single-precision floating point value.
32 * Anything out of range (including NaN and infinity) should return
33 * 0x80000000u.
34 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
35 * Max ops: 30
36 * Rating: 4
37 */
38int floatFloat2Int(unsigned uf)
39{
40 int s_ = uf >> 31;
41 int exp_ = ((uf & 0x7f800000) >> 23) - 127;
42 int frac_ = (uf & 0x007fffff) | 0x00800000;
43 if (!(uf & 0x7fffffff))
44 return 0;
45
46 if (exp_ > 31)
47 return 0x80000000;
48 if (exp_ < 0)
49 return 0;
50
51 if (exp_ > 23)
52 frac_ <<= (exp_ - 23);
53 else
54 frac_ >>= (23 - exp_);
55
56 if (!((frac_ >> 31) ^ s_))
57 return frac_;
58 else if (frac_ >> 31)
59 return 0x80000000;
60 else
61 return ~frac_ + 1;
62}
63/*
64 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
65 * (2.0 raised to the power x) for any 32-bit integer x.
66 *
67 * The unsigned value that is returned should have the identical bit
68 * representation as the single-precision floating-point number 2.0^x.
69 * If the result is too small to be represented as a denorm, return
70 * 0. If too large, return +INF.
71 *
72 * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
73 * Max ops: 30
74 * Rating: 4
75 */
76unsigned floatPower2(int x)
77{
78 int exp = x + 127;
79 if (exp <= 0)
80 return 0;
81 if (exp >= 255)
82 return 0x7f800000;
83 return exp << 23;
84}