int 部分
bitXor
- bitXor - 仅允许使用~和&来实现异或
- 例子: bitXor(4, 5) = 1
- 允许的操作符: ~ &
- 最多操作符数目: 14
solution:
int bitXor(int x, int y) {
return ~(~(x & ~y) & ~(~x & y));
}tmin
- tmin - 返回最小的二进制补码
- 允许的操作符: ! ~ & ^ | + << >>
- 最多操作符数目: 4
solution:
一个 int是四个字节，故最小的补码就是 1 << 31
int tmin(void) {
return 1 << 31;
}isTmax
- isTmax - 如果x是最大的二进制补码，返回1；否则，返回0
- 允许的操作符: ! ~ & ^ | +
- 最多操作符数目: 10
solution:
判断是否最大的补码，不能使用移位符号，所以利用最小值翻倍溢出进行判断：
最大补码 0x7fffffff ，加一后会溢出成最小值 0x10000000 ，再乘二就会溢出成 0 。所以可以按照这个思路来判断。这里有个特殊情况 -1 ，因为 -1 加一后变成 0 ，0 乘二还是 0 ，所以需要特殊判断。
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 即可。
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:
取反再加一即可。
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 码再加一) 进行相减，之后再比较其最高位即可。
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 操作即可。
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 成立即可。
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 的前后两部分进行或操作，直到剩下一位为止。接着再对这一位进行判断。
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位中。将这个过程递归地做下去即可找到最高有效位。
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，所以需要将尾数域置零。
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位。
最后将三个合并在一起即可。
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。
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;
}