1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252

//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) {
  //   x^y 
  // = (~x&y)|(x&~y) // 异或公式
  // = ~(~(~x&y)&~(x&~y)) // 德摩根律，ops: 8
  // = ~((x|~y)&(~x|y)) // 德摩根律
  // = ~(x&~x|x&y|y&~y|~x&~y) // 分配律
  // = ~(x&y|~x&~y) // 吸收率
  return ~(x&y)&~(~x&~y); // 德摩根律，ops: 7
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  // For negative numbers: complement = inverse + 1
  return 1 << 31; // tmin=0x80, tmax=0x7f
  // 为什么是补码？
  // 为了方便计算机处理，我们希望负数和其相反数相加之后自然的溢出得0。
  // x+~x=1, 再加1则溢出得0。因此补码=反码+1。
  // 同时符号位天然的蕴含在最高位上，这有许多好处。
  // 其一是正数的表现和无符号整数一致。
  // 其二是由于＋0和-0一致，相比显式符号位能多表示一个数字，范围是[-2^(n-1),2^(n-1)-1]
}
//2
/*
 * 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) {
  // ! 逻辑取反，仅全0返回1，其余情况都返回0
  // ~ 按位取反
  // 补码相反数 = 反码 + 1
  // 两个特例：~tmin+1=tmin; ~0+1=0. 相反数为自身 
  // 得到几个函数：
  // negate(x) (~x+1) // 取相反数
  // iszero(x) (!!x) // 仅当!!0=0
  // equal(x,y) !(x^y) // 判断相等
  // ~tmax=tmin, 转换为筛选tmin和0xff
  // 因此答案为 equal(~x,negate(~x)) & iszero(~x)
  return !((x+1)^(~x)) & (!!~x); // ops: 8
}
/* 
 * 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) {
  // 掩码: x & 0b1111, 结果相当于只取了x的后4位
  // 奇数位全为1，使用掩码0xAAAAAAAA提取奇数位，再使用equal(x,0xAAAAAAAA)判断即可
  int mask = 0xAA;
  mask += mask << 8;
  mask += mask << 16;
  return !(x&mask ^ mask);  // ops: 7
} 
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x+1;
}
//3
/* 
 * 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 > y
  // => x+(~y+1) > 0 // x+(-y)>0
  // => !(x+(~y+1) >> 31) // 使用符号位判断>0
  // 得到比较函数：
  // gpos(x, y) !(x+(~y+1) >> 31)
  // 带入即可 !((0x39 + ~x+1)>>31) & !((x + ~0x30+1)>>31) // ops: 11
  return !((~x+0x3A)>>31) & !((x + ~0x30+1)>>31); // ops: 10
} 
/* 
 * 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) {
  // 或运算两侧不同时为1即可构成条件判断，使用掩码控制输出内容
  // 错误做法：
  // int mask = x >> 31; // 算数右移取符号位填充全部位
  // x ? y : z 对x是逻辑判断不是算术判断
  int mask= ~!x+1; // 仅0返回1
  return (~mask&y)|(mask&z) ; // ops: 7
}
/* 
 * 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) {
  // gpos(x, y) 在跨符号的情况下失灵，增加两种情况判断:
  // 1. x=y：返回1
  // 2. x和y不同符号：x为负时一定小于，返回1，x符号位也是1
  // 因此答案为 equal(signx,signy) ? (gpos(y,x) | equal(x,y)) : signx
  int signx=!!(x>>31), signy=!!(y>>31);
  int mask = (signx^signy);
  return  (!mask & (!(y+(~x+1)>>31)) | !((x)^(y))) | (mask&signx); // ops: 19
}
//4
/* 
 * 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返回1，其余返回0
  // 还是借助两个特例：~tmin+1=tmin; ~0+1=0. 相反数为自身
  // 答案为 equal(x,~x+1) & !equal(x,tmin) 
  // !(x^0) & !!(x^(1<<31))
  return !((x^0) | !(x^(1<<31))); // ops: 6
}
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5 // [-16,15]
 *            howManyBits(298) = 10 // [-512,511]
 *            howManyBits(-5) = 4 // [-8,7]
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1 // [-1,0]
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  // 负数取反，统一处理
  // x>>31 ? ~x:x = x>>31 & ~x | ~(x>>31) & x
  x = x>>31^x; 
  // 位宽取决于最高位，问题转化为寻找最高位
  // 90个操作符不足以遍历32个位，因此需要优化搜索算法，如二分。
  // !!(x>>16) 判断x的高16位是否存在1
  int b16 = !!(x>>16) << 4;   
  // 若存在，至少需要16位，因此b16赋值为16或0
  x = x >> b16; 
  // 通过移位实现二分搜索：
  // 若高位存在则舍弃低位，高位全0则判断低位
  int b8 = !!(x>>8) << 3;
  x = x >> b8;
  int b4 = !!(x>>4) << 2;
  x = x >> b4;
  int b2 = !!(x>>2) << 1;
  x = x >> b2;
  int b1 = !!(x>>1);  x = x >> b1;

  return b16+b8+b4+b2+b1+x+1;
}
//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
 */
unsigned floatScale2(unsigned uf) {
    unsigned s = uf & (1 << 31);
    unsigned exp = (uf & 0x7f800000) >> 23;
    unsigned frac = uf & (~0xff800000);

    if (exp == 0) return frac << 1 | s; // 非规格数乘2即可
    if (exp == 255) return uf;  //  特殊值直接返回
    exp++;
    if (exp == 255) return 0x7f800000 | s;  // 乘法不可能得到NaN，所以返回无穷
    return s | (exp << 23) | frac;
}
/* 
 * 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) {
    unsigned s = uf & (1 << 31);
    unsigned exp = (uf & 0x7f800000) >> 23;
    unsigned frac = uf & (~0xff800000);

    int E = exp - 127;
    if (exp == 255 || E > 31) return 0x80000000;  // 特殊值
    if (E < 0) return 0; // 小数舍入为0

    unsigned M = frac | (1 << 23);  // 1 + frac
    int V = (E > 23 ? M << (E - 23) : M >> (23 - E)); // M已经被左移了23位
    if (s) V *= -1;  // 负数
    return V;
}
/* 
 * 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) {
    // V = (-1)^s * M * 2^E 
    // E = e-127  E∈[-126,127]
    // s=0,f=0, x带入E即可得到 2^x
    // 为此，反演从E求e的过程
    if (x >= 128) return 0x7f800000;  // +INF
    if (x >= -126) return (x + 127) << 23; // [-126,127]: 2^x为规格数, f=1.0, e=x+127
    if (x >= -150) return 1 << (x + 150); // [-150,-125]: 2^x为非规格数, f=2^(x+150), e=0
    else return 0; // too small
}