Loading... ## int 部分 ### bitXor * bitXor - 仅允许使用~和&来实现异或 * 例子: bitXor(4, 5) = 1 * 允许的操作符: ~ & * 最多操作符数目: 14 **solution: ** ```c int bitXor(int x, int y) { return ~(~(x & ~y) & ~(~x & y)); } ``` ### tmin * tmin - 返回最小的二进制补码 * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 4 **solution: ** 一个 int是四个字节，故最小的补码就是 1 << 31 ```c int tmin(void) { return 1 << 31; } ``` ### isTmax * isTmax - 如果x是最大的二进制补码，返回1；否则，返回0 * 允许的操作符: ! ~ & ^ | + * 最多操作符数目: 10 **solution: ** 判断是否最大的补码，不能使用移位符号，所以利用最小值翻倍溢出进行判断： 最大补码 0x7fffffff ，加一后会溢出成最小值 0x10000000 ，再乘二就会溢出成 0 。所以可以按照这个思路来判断。这里有个特殊情况 -1 ，因为 -1 加一后变成 0 ，0 乘二还是 0 ，所以需要特殊判断。 ```c int isTmax(int x) { return (!(x + 1 + x + 1)) & (!!(x + 1)); } ``` ### allOddBits * allOddBits - 如果所有奇数位都为1则返回1;否则返回0 * 例子： allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 12 **solution: ** 递归地将 x 的前半部分和后半部分进行 and 操作，剩余两位的时候判断较高位是否为 1 即可。 ```c int allOddBits(int x) { x &= x << 16; x &= x << 8; x &= x << 4; x &= x << 2; x &= 1 << 31; return !!x; } ``` ### negate * negate - 返回-x * 例子: negate(1) = -1. * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 5 **solution: ** 取反再加一即可。 ```c int negate(int x) { return ~x + 1; } ``` ### isAsciiDigit * isAsciiDigit - 如果x是ascii码中的0~9，返回1;否则返回0 * 例子: isAsciiDigit(0x35) = 1. * isAsciiDigit(0x3a) = 0. * isAsciiDigit(0x05) = 0. * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 15 **solution: ** 将 x 与 0x30 (0 的 ASCII 码) 和 0x3A (9 的 ASCII 码再加一) 进行相减，之后再比较其最高位即可。 ```c int isAsciiDigit(int x) { int min = ~0x30 + 1 + x; int max = ~0x3A + 1 + x; min = ~min & (1 << 31); max &= 1 << 31; return !!(min & max); } ``` ### conditional * conditional - 实现x?y:z * 例子: conditional(2,4,5) = 4 * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 16 **solution: ** 这道题要进行判断，很容易想到利用逻辑非来将输入转化为 0 或 1 。接下来可以利用取反加一的方式来将输入转化为全0或全1 。最后根据条件将 y 和 z 和处理后的 x 进行 and 操作即可。 ```c int conditional(int x, int y, int z) { x = !x; // convert to 0 or 1 x = ~x + 1; return (y & ~x) | (z & x); } ``` ### isLessOrEqual * isLessOrEqual - 如果x<=y返回1否则返回0 * 例子: isLessOrEqual(4,5) = 1. * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 24 **solution: ** 要求 x <= y ，可以转化为 !(x > y) 方便求解。 对 x，y 的符号进行讨论: 当 x, y 同号时: 此时 x > y 只有一种情况，即 x > 0 且 y < 0。 当 x, y 异号时: 此时 x > y ，即 x – y >0 成立即可。 ```c int isLessOrEqual(int x, int y) { int case1 = ~x & y; int case2 = ~(x ^ y) & (y + ~x + 1); return !((case1 | case2) >> 31); } ``` ### logicalNeg * logicalNeg - 实现！运算符的功能 * 例子: logicalNeg(3) = 0, logicalNeg(0) = 1 * 允许的操作符: ~ & ^ | + << >> * 最多操作符数目: 12 **solution: ** C语言中逻辑非操作的输入非0则返回1，故只要一个数的二进制含有1，那么逻辑非就应该返回0 。因此可以递归地将 x 的前后两部分进行或操作，直到剩下一位为止。接着再对这一位进行判断。 ```c int logicalNeg(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x |= x >> 1; return (x & 1) ^ 1; } ``` ### howManyBits /* howManyBits - 返回将X表示为补码所需的最小有效位数。 * 例子: howManyBits(12) = 5 * howManyBits(298) = 10 * howManyBits(-5) = 4 * howManyBits(0) = 1 * howManyBits(-1) = 1 * howManyBits(0x80000000) = 32 * 允许的操作符: ! ~ & ^ | + << >> * 最多操作符数目: 90 **solution: ** 这道题目求表示为补码所需的最小有效位数，那么就将输入 x 分情况讨论: 首先是x为正数时。此时求出最小有效位数只需要找出x的最高有效位再加上符号位即可。如 5 = 0b0101，最高有效位为3，加上符号位需要4位。 接下来看 x 为负数的时候。举个例子 x = -7 = 0b1001，取反再加一得到 0b0111。此时就可以套用正数的想法了。但是对于某些特殊的负数，如 x = -8 = 0b1000，它取反再加一还是0b1000，此时就不好判断了。所以按照正常的取反加一可能会导致误判。因此可以舍去加一，直接对负数取反。这样就可以直接套用正数的想法了。 对于两个特殊的数 0，-1，也可以归到上面两种情况里。0 最高有效位是0，加上符号位，需要1位即可。-1 取反后为0。所以这两个数也可以正常判断。 最后的问题就是如何找到最高有效位了。这里可以使用二分和递归的思想: 将一个数二分为高16位和低16位，并判断高16位是否为0。若高位为0则最高有效位在低16位中，反之则在高16位中。将这个过程递归地做下去即可找到最高有效位。 ```c int howManyBits(int x) { int input = (x >> 31) ^ x; int res = 0; int tmp = 0; tmp = !!(input >> 16) << 4; res += tmp; input >>= tmp; tmp = !!(input >> 8) << 3; res += tmp; input >>= tmp; tmp = !!(input >> 4) << 2; res += tmp; input >>= tmp; tmp = !!(input >> 2) << 1; res += tmp; input >>= tmp; tmp = !!(input >> 1); res += tmp; input >>= tmp; res += input; return res + 1; } ``` ## float 部分 ### float_twice * float_twice - 以unsinged表示的浮点数二进制的二倍的二进制unsigned型 * 参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值。 * 允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while * 最多操作符数目: 30 **solution: ** 要求计算浮点数的两倍。根据 IEEE754 的规定，单精度浮点数的第 23~30 位数表示浮点数的指数。所以一般情况下让这个数 +1 即可实现乘二。 但是这只是一般情况，还需要考虑特殊情况: 当输入是 0 (0x0) 或 -0 (0x80000000) 时，乘二的结果即为本身。 当 23~30 位全是 1 时，输入是 无穷 或 NaN ，直接返回本身即可。 当 23~30 位全是 0 时，输入为非规约数，此时直接将尾数域加倍即可。 当指数位 +1 后 23~30 位全是 1 时，结果应为无穷而不是 NaN，所以需要将尾数域置零。 ```c unsigned float_twice(unsigned uf) { if (uf == 0 || uf == 1 << 31) return uf; if (((uf >> 23) & 0xff) == 0xff) return uf; if (((uf >> 23) & 0xff) == 0) return (uf & (1 << 31)) | (uf << 1); uf += 1 << 23; if (((uf >> 23) & 0xff) == 0xff) uf &= 0xff800000; return uf; } ``` ### float_i2f * float_i2f - 返回int x的unsigned浮点数的二进制形式 * 参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值 * 允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while * 最多操作符数目: 30 **solution: ** 这道题目要求将整数转化为浮点数的存储方法。 首先对 0 进行讨论。 0 无法使用 底数 + 指数 的方法表示，所以直接返回0。 浮点数的底数是非负的，所以需要对输入取绝对值。而 0x80000000 在 int 中不存在绝对值，故这个数要特殊处理。 接下来就是一般情况的转换： 首先取出输入的符号并将其取绝对值。 接着找出最高有效位作为指数。 对于尾数需要分情况讨论： 当数据位小于等于 24 位时，直接将其作为尾数即可。(注意最高位置零) 当数据位大于24位时，需要根据二进制的舍入规则将数据保留成 24位。 最后将三个合并在一起即可。 ```c unsigned float_i2f(int x) { if (x == 0) return 0; if (x == 0x80000000) return 0xcf000000; int sign = x & 0x80000000; int digits = 0; if (sign) x = -x; int tmp = x; while (tmp >>= 1) digits += 1; int exponent = ((digits + 127) & 0xff) << 23; int fraction = x ^ (1 << digits); int bits = digits + 1; if (bits <= 24) fraction <<= 24 - bits; else { int abandoned = digits - 23; int mid = 1 << (abandoned - 1); int discard_digits = ~(-1 << abandoned) & fraction; fraction >>= abandoned; if ((discard_digits > mid) || (discard_digits == mid && (fraction & 1))) fraction += 1; } return (sign | (exponent + fraction)); } ``` ### float_f2i * float_f2i - 返回unsigned uf的整型数的二进制形式 * 参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值 * 任何超过范围的数都应该返回 0x80000000u. * 允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while * 最多操作符数目: 30 **solution: ** 将浮点数转化为整数，超过范围的数返回 0x80000000。 根据 IEEE754 的规定，一般情况将浮点数转化为整数需要分离符号，指数，尾数即可。下面对特殊情况进行讨论: 浮点数为 0 或 -0 时，直接返回 0 。 指数全为 1 时，超出范围，返回 0x80000000。 因为转化为整数，所以小数的部分直接舍去。因此实际指数小于 0 的话直接返回 0 。 单精度浮点数位数只有23位，所以实际指数小于 23 的话应向右移动，反之则向左移动。 int 型数据最大位数为 31 位 (不包括符号) ，所以实际指数应小于31，超过的直接返回 0x80000000。 ```c int float_f2i(unsigned uf) { if (uf == 0 || uf == 0x80000000) return 0; int sign = uf & (1 << 31); int exponent = (uf >> 23) & 0xff; int fraction = (uf & 0x7fffff) + 0x800000; int res = 0; if (exponent == 0xff) return 0x80000000; exponent -= 127; if (exponent < 0) return 0; else if (exponent <= 23) res = fraction >> (23 - exponent); else if (exponent <= 30) res = fraction << (exponent - 23); else return 0x80000000; if (sign) res = -res; return res; } ``` 最后修改：2020 年 04 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏