题目
Integer
这一部分的函数感觉很需要构造思维，部分函数写起来有些吃力。
bitXor
要求只使用 ~ (取反) 和 & (按位与) 实现异或。
比较简单的一个函数，实现很简洁：
int bitXor(int x, int y) {
return ~(x & y) & ~(~x & ~y);
}
由于使用的都是按位运算，因此可以拆位进行考虑，即简化 x,y \in \{0, 1\} 的情况。
根据定义，当且仅当 x=1, y=1 时，x \wedge y=1，同理有 x=0, y=0 时，\neg x \wedge \neg y=1。
对两种运算取反并取交集（也就是再做一次或运算），就可以得到异或了。
（本质上是德摩根定律）
tmin
要求输出 int32 类型的最小值。
直接返回 1 << 31 即可。
int tmin(void) {
return 1 << 31;
}
isTmax
要求不使用移位运算，判断一个数是否为 int32 类型的最大值。
如果可以使用位运算的话，显然有 T_{max}=2^{31}-1，即 (1 << 31) - 1 ，接下来只需要想办法判断 x 是否等于 T_{max} 就可以了。
但是这个函数不能使用位运算，需要另辟蹊径。个人想法是取 2x+1，在 32 位补码下，有 2T_{max}+1=2^{32}-1=-1，得到一个充分条件 2x+1=-1。由于对 -1 取反会得到 0，对其他数取反均为非 0，可以很快写出对应的表达式： !~(x + 1 + x) 。
但是很显然没有完事，上述式子不具有必要性。容易发现 -1 也满足上述式子，因此只需要用同样的方法判断 x\neq-1 即可。
int isTmax(int x) {
return !!(x + 1) & !~(x + 1 + x);
}
allOddBits
要求判断一个数的二进制奇数位是否全为 1。
注意到注释给出 allOddBits(0xAAAAAAAA) = 1，而 0xAAAAAAAA 正好是一个奇数位全为 1，偶数位全为 0 的数，因此只需要判断 x\wedge(AAAAAAAA)_{16}=(AAAAAAAA)_{16} 就行了。
然而可用的整数范围只有 [0,2^{8}-1]，即 unsigned char 的范围。为此只能通过移位运算拼出 0xAAAAAAAA 。接下来判断两数相等就简单了，注意到其充要条件是其中一个数与另一个数补码的 按位或 等于 -1，判断 -1 直接用上面的方法就可以了。
int allOddBits(int x) {
int mask = 0xAA << 24 | 0xAA << 16 | 0xAA << 8 | 0xAA;
return !~((x & mask) | ~mask);
}
negate
要求对一个数取相反数并返回。
非常简单的函数，根据相反数与补码的关系很快就能写出来。
int negate(int x) {
return ~x + 1;
}
isAsciiDigit
要求判断一个数对应的 ASCII 码是否为数字（即判断 (30)_{16}\leq x\leq (39)_{16} 是否成立）。
比较复杂的一个函数。注意到只有最后一个十六进制位可变，其余位都是固定的，因此可以将这个数拆成两部分进行判断。拆位的方法就是直接将 x 与 (F)_{16} 做按位与即可得到低位，对 (F)_{16} 额外取一步补码即可得到高位。
对于高位，直接判断其是否等于 (30)_{16} 即可，但是由于只取了一个数的部分位，不能直接用补码判断相等。这里用到了异或的性质 x\oplus x=0，即判断相等只需要看异或后的数是否为 0。
低位的情况比较复杂，这里再分成两种情况。设低位为 l，当 l\in[0,7] 时，显然有 l\wedge8=0，直接判断是否满足即可。当 l\in[8,9] 时，第 2 位和第 1 位一定为 0，第 0 位可以任取，判断这两位是否为全 1 即可。
低位的第一个判断条件如果成立会返回 8，要通过做两次非运算或者右移 3 位转化为 1 。
int isAsciiDigit(int x) {
int x_high = x & ~0xF;
int x_low = x & 0xF;
int high_bit = !(x_high ^ 0x30);
int low_bit = (~x_low & 0xF) >> 3 | !(x_low & 0x6);
return high_bit & low_bit;
}
Conditional
要求实现三目运算符。
第一眼感觉比较复杂，但是思路出来以后感觉不算难的函数。
首先引入两个变量 isTrue 和 isFalse，x 为真时令 isTrue=-1,isFalse=0，x 为假时反过来。接下来考虑如何实现。
通过对 x 取非再加上 -1 ，就能得到 x 为真时 isTrue=-1，反之 isTrue=0，isFalse 直接对 isTrue 取反就行。
考虑如何实现条件控制。因为 -1 的二进制补码为全 1， 0 的二进制补码为全 0，前者与一个数进行按位与运算不会使数改变，后者进行按位与运算结果一定为 0。因此直接用 y 按位与 isTrue，z 按位与 isFalse，当 x 为真时 y 被保留， z 变成 0，反之亦然。最后直接将两数按位或即可。
int conditional(int x, int y, int z) {
int is_true = !x + ~0; // true is -1
int is_false = !!x + ~0; // false is -1
return (y & is_true) | (z & is_false);
}
isLessOrEqual
要求判断 x\leq y 是否成立。
第一眼想法是先判断符号位，若符号位相同再利用 y-x 的符号判断两数大小，这样一来符号位相同的数最多相差 2^{31}-1 ，可以避免溢出造成的影响。
实现时要利用到上一个函数中实现的条件控制，分为 eq（判断 y-x 是否为正） 和 neq （判断 x 是否为负）两种情况。符号相同时输出 eq ，否则输出 neq。
int isLessOrEqual(int x, int y) {
int x_sign = x >> 31;
int y_sign = y >> 31;
int eq = !((y + ~x + 1) >> 31);
int neq = x_sign & 1;
int is_true = !!(x_sign ^ y_sign) + ~0;
int is_false = !(x_sign ^ y_sign) + ~0;
return (eq & is_true) | (neq & is_false);
}
LogicalNeg
要求实现逻辑非，即判断 x=0 是否成立。
在这个地方卡题了，想了很久才发现和前面的 0 具有一个性质，就是其相反数就等于它本身，但是同时 -2^{32} （也就是 T_{min}）在 32 位补码下的相反数也等于它本身，因此还需判断其是否等于 T_{min}。IsTmax 差不多。
int logicalNeg(int x) {
return ~(((~x + 1) ^ x) >> 31) & 1 & ~(x >> 31);
}
howManyBits
要求返回表示 x 所需要的最小补码位数。
首先表示负数的最小补码位数和其取反后对应的非负数的最小补码位数是相等的，因此第一步可以对负数先取反。
接下来考虑如何判断补码位数。显然有一个暴力做法，即直接枚举最高位的 1 所在的位置。题目要求是使用最多 90 个运算符，看似很宽松，实际上如果直接暴力判断的话数量仍然比较紧张，因此考虑二分。
Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
–Um_nik
由于不能使用循环，只能手搓二分。方法是从 mid=16 开始（即假定 l=0,r=31），每次不断缩小范围，直到进行五次后得到 res=l=r，最后输出 res+1 （+1 是因为最低位从 0 开始）。
int howManyBits(int x) {
int res = 0;
x = x ^ (!(x >> 31) + ~0);
// Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
// 16
int x16 = !!(x >> res + 15);
res = res + (x16 << 4);
// 8
int x8 = !!(x >> res + 7);
res = res + (x8 << 3);
// 4
int x4 = !!(x >> res + 3);
res = res + (x4 << 2);
// 2
int x2 = !!(x >> res + 1);
res = res + (x2 << 1);
// 1
int x1 = !!(x >> res);
res = res + x1;
return res + 1;
}
Float
浮点数部分几乎没啥限制了，写起来比前面舒服很多。
FloatScale2
要求返回 2*f，若原先为 NaN 则返回 NaN。
这个浮点数被存储到了一个 unsigned int 类型里，因此可以直接通过位运算拆位，然后主要针对阶码进行判断。
首先判断是否为非规格化数，如果是则直接左移 1 位即可（非规格化数与阶码最小的规格化数的精度是一样的，且非规格化数阶码为 0，因此可以直接左移，最后再加上符号即可）。
若为规格数，则要分两种情况：第一种为阶码小于 11111110 （即规格化数可用的最大的阶码），根据阶码定义，直接将阶码位 +1 即可。第二种为阶码位等于 11111110，此时再乘 2 只会得到 Infinity，因此要返回 0x7f800000u （即 Infinity 对应的补码）。
对于 Infinity 和 NaN（即所有阶码位为全 1 的情况），直接输出本身即可。
unsigned floatScale2(unsigned uf) {
unsigned t_min = 1 << 31;
unsigned t_max = t_min - 1;
unsigned sign = uf & t_min;
unsigned exp = (uf & t_max) >> 23;
unsigned base = uf & ((1 << 23) - 1);
if (exp) {
if (exp < 254) {
return sign | exp + 1 << 23 | base;
} else if (exp == 254) {
return sign | 0x7f800000u;
} else if (exp == 255) {
return uf;
}
} else {
return (uf << 1) | sign;
}
}
floatFloat2Int
要求返回 (int)f，即将浮点数强转为整数的结果。
由于是向零取整，因此对于阶码小于 127 的情况直接返回 0 （因为这些数的绝对值都小于 1）。
对于阶码不小于 127 的情况作分类讨论：如果阶码大于等于 127+32=159，说明该数的绝对值不小于 2^{32}，直接返回 0x80000000u。如果阶码在 [127,159] 的范围内，就对尾数从高位到低位枚举，小于 2^{0} 的情况直接舍去即可。
int floatFloat2Int(unsigned uf) {
unsigned t_min = 1 << 31;
unsigned t_max = t_min - 1;
unsigned sign = (uf & t_min) ? -1 : 1;
int exp = ((uf & t_max) >> 23) - 127;
unsigned base = uf & ((1 << 23) - 1);
if (exp < 0) {
return 0;
} else if (exp < 32) {
int res = 1 << exp;
int i = 22;
while (i >= 0) {
if (base >> i & 1) {
int bit = exp + i - 23;
if (bit >= 0) {
res += 1 << bit;
}
}
--i;
}
return sign * res;
} else {
return 0x80000000u;
}
}
floatFloat2Int
要求返回 2^{x}。
首先考虑规格化数，即 -126\leq x\leq 127 的情况，这时显然只有阶码存在 1 ，且阶码等于 x 与偏置值之和。
对于非规格化数，其只会有一位是 1 且这一位一定在尾数上，可以直接对最小的规格化数（即 2^{-126} ）左移位得到，对于很小的 x 直接输出 0，以免左移位太多出现 UB。
对于 x>127 的情况，直接输出 Infinity 。
unsigned floatPower2(int x) {
if (x < -126) {
int d = -126 - x;
return d >= 23 ? 0 : 0x00800000u >> d;
} else if (x <= 127) {
return (x + 127) * 0x00800000u;
} else {
return 0x7f800000u;
}
}
评论