Data Lab
Last updated on February 8, 2024
bitXor(x, y)
描述：只用 ~ 和 & 实现 ~(x|y)
思路：由反演定理，直接得出 ~(x|y) = ~x & ~ycopyLSB(x)
描述：将 x 的所有位都设置为它的最低位的值
思路：利用移位的性质，先将 x 的最低位左移到最高位，再算术右移回来。这样，如果该位是 0 就全为 0，如果是 1 就全补 1。isEqual(x, y)
描述：x==y 返回 1，否则返回 0
思路：考虑 x==y，可以利用按位异或 ^ 的运算，x==y 时结果为全 0，否则有 1。再跟一个逻辑非 ! 的操作，全 0 则返回 1，否则返回 0。bitMask(highbit, lowbit)
描述：生成一个掩码，lowbit 位至 highbit 位均为 1
思路：要产生这样一个 low 到 high 均为 1，其余位为 0 的掩码，同样可以利用按位异或 ^ 运算。将一个全 1 的序列分别左移 low 和 high+1 位后再进行异或，就把中间不一致的那一段置为 1，其余为 0。此外，要考虑 lowbit > highbit 的特殊情况，就再补上一个 & low。bitCount(int x)
描述：计算 x 中 1 的数目
思路 - baseline：采用分治的思想，制作出一个 mask，得出 x 的每字节中 1 的数目，然后将结果折叠到低 8 位中。tmax()
描述：返回最大的补码
思路：最大的补码即 0x7FFFFFFF,可以由 0x80000000 取反得到。isNonNegative(x)
描述：如果 x>=0，返回 1，否则返回 0
思路：x 是否非负要看符号位是否为 1，首位右移 31 位再逻辑非 ! 即可。addOK(x, y)
描述：确定 x+y 是否不溢出
思路：有符号数加法溢出的表现是：两数同号，而与其和异号。据此判断即可。rempwr2(x, n)
描述：计算 x % (2^n)
思路 - baseline：要计算这个模，对于正数只需取出 x 的低 n 位。考虑负数的情况，可以通过取反加 1 将其转为正数，取出低 n 位，再取反加 1 转回负数。因为不能使用 if 语句，所以将这两种情况统一到绝对值的操作，见第 11 问。isLess(x, y)
描述：如果 x<y，返回 1，否则返回 0
思路：要判断两数大小，异号时直接得出结果，同号时可以借助 x-y 的符号判断。absVal(x)
描述：x 的绝对值
思路：若是正数保持不变，若是负数取反加一。可以通过对 x >> 31 的运算统一这两种操作。isPower2(x)
描述：如果 x 是 2 的幂，返回 1，否则返回 0
思路：即判断 x 除了为 0 的符号位外，是否仅由单独的一位 1 组成。在排除了 x<0 和 x=0 的情况后，对于正数 x，!(x & (x + (~0))) 即可判断是否只有一个 1。float_neg(uf)
描述：计算 -f
思路：位级表示的浮点数，求负数直接符号位取反即可。此外，需要排除为 NAN 的情况，即判断阶码段 E 全 1 且尾数段 M 不为 0。float_half(uf)
描述：返回 0.5*f 的位级表示
思路：对于规格化的情况，除以二相当于在阶码段 E 减 1。考虑为 inf 或 NAN 的情况，判断阶码段 E 为全 1 则直接返回；考虑结果为非规格化的情况，除以二相当于右移一位，还需要考虑浮点数向偶数舍入的要求，判断低二位为 11 时需要打个补丁让结果的最低位为 0。float_i2f(x)
描述：返回 (float)x 的位级表示
思路：如果 x 是 0 直接返回。对于非 0 的情况，通过看 x 除符号位外的第一个 1 在第几位，得到阶码段 E 的值。然后从 x 中摘出尾数段 M 的值。因为要舍去 x 的末 9 位，还要考虑舍入打个补丁。
参考：