[数据结构与算法]实验 1 ：Data Lab

bitXor(x, y)

使用 ~ 和 & 实现异或操作，返回 $x\oplus y$

int bitXor(int x, int y) {
    return ~(~x & ~y) & ~(x & y);
}

根据异或的运算规则，我们只需要将不同时为 $0$ 的位和不同时为 $1$ 做与操作。

tmin()

返回最小的整数补码

int tmin(void) {
    return 1 << 31;
}

补码带有符号位，最小的整数补码只有符号位为 $1$ ，其他位为 $0$ 。

isTmax(x)

当 $x$ 为最大的整数补码时返回 $1$ ，否则返回 $0$

int isTmax(int x) {
    int tmin = x + 1;
    x = x + tmin;
    x = ~x;
    tmin = !tmin;
    x = x + tmin;
    return !x;
}

最大的整数补码为 011111…，因此我们的目的就是将 $x$ 变为 $0$ 。不妨假设 $x$ 为最大整数补码。第一步加 $1$ 后就变成了 $T_{min}$ ，此时 $x+T_{min}$ 就等于 $?1$ ，取反后就变成了 $0$ 。

但是还有一种特殊情况，当 $x=?1$ 时，仍然可以通过前面的步骤来变成$0$，所以我们就要对这种情况进行额外判断，此时 $tmin$ 的值为 $0$ ，进行非操作后就变成了 $1$ ，与 $x$ 相加后就不等于 $0$ ，可以排除这种情况。

allOddBits(x)

$x$的奇数位都为$1$时返回$1$，否则返回$0$

int allOddBits(int x) {
    int c = 0x55;
    c = c + (c << 8);
    c = c + (c << 16);
    return !((x & (~c)) ^ (~c));
}

首先将数字变成 0x55555555 的形式，取反后为 0xAAAAAAAA ，如果 $x$ 的奇数位都为 $1$ ，那么与 0xAAAAAAAA 与操作后仍为 0xAAAAAAAA，通过异或进行判断。

negate(x)

返回 $?x$

int negate(int x) {
    return ~x + 1;
}

isAsciDigit(x)

当 $48\le x\le 57$ 时返回 $1$ ， 否则返回 $0$

int isAsciiDigit(int x) {
    int a = !(x >> 4 ^ 0x3);
    int b = !((x & 0xa) ^ 0xa);
    int c = !((x & 0xc) ^ 0xc);
    return a & !(b | c);
}

要想完成这个目的，我们需要进行两个判断：低 $4$ 位满足大于等于 $0$ 并且小于等于 $9$ ，高四位等于 $3$ 。

对于低四位，如果不满足这个条件，那么它对应的位为 0xa 或0xc ，可以通过异或进行判断，对于高四位，可以通过移位加上异或来判断。

conditional(x, y, z)

等同于 x ? y : z 这样的操作

int conditional(int x, int y, int z) {
    x = !!x;
    x = ~x + 1;
    return (x & y) | (~x & z);
}

这道题如果想到了把 $x$ 变成全 $0$ 或者全 $1$ 的形式就会比较容易做，通过前两行代码，当 $x=0$ 时，$x$ 的二进制位就是全 $0$ 的，否则是全 $1$ 的形式。

isLessOrEqual(x, y)

当 $x\le y$ 时返回 $1$， 否则返回 $0$

int isLessOrEqual(int x, int y) {
    int neg_x = ~x + 1;
    int sub_x = y + neg_x;
    int tmin = 1 << 31;
    int xsign = !!(x & tmin);
    int ysign = !!(y & tmin);
    int sub_x_sign = sub_x & tmin;
    return (!(xsign ^ ysign) & !sub_x_sign) | ((xsign ^ ysign) & xsign);
}

分符号位相同和符号位不同来分类讨论，符号位相同时，需要满足 $y?x\ge 0$ ；符号位不同时，需要满足 $x<0$。

logicalNeg(x)

不用 ！运算符来实现 ！的功能

int logicalNeg(int x) {
    int c = ~x + 1;
    return ((x | c) >> 31) + 1;
}

当 $x=0$ 时，$?x=x$ ，我们可以利用这个性质来实现 ！运算符的功能。

howManyBits(x)

用补码表示 $x$ 的最小位数

int howManyBits(int x) {
    int bit0, bit1, bit2, bit4, bit8, bit16;
    int sgn = x >> 31;
    x = (~sgn & x) | (~x & sgn);
	//判断高16位是否存在1,如果存在,则说明最少有16位,下面同理
    bit16 = !!(x >> 16) << 4;
    x = x >> bit16;
    bit8 = !!(x >> 8) << 3;
    x = x >> bit8;
    bit4 = !!(x >> 4) << 2;
    x = x >> bit4;
    bit2 = !!(x >> 2) << 1;
    x = x >> bit2;
    bit1 = !!(x >> 1);
    x = x >> bit1;
    bit0 = x;
    return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1;
}

对于正数来说，我们需要找到最高位的 $1$ 所在的位置，然后加上符号位。对于负数，我们需要找到最高位的 $0$ 所在的位置，然后加上符号位。对于负数的情况，我们可以进行转换，把 $0$ 变成 $1$，把 $1$ 变成 $0$ ，这样就变成了正数的情况。

floatScale2(uf)

对于浮点参数 f，返回 2*f 的位级等价数

unsigned floatScale2(unsigned uf) {
    unsigned sign = uf & (1 << 31);
    unsigned e = (uf & 0x7f800000) >> 23;
    if(e == 0xff) return uf;
    if(e == 0) return sign | uf << 1;
    e++;
    if(e == 0xff) return sign | 0x7f800000;
    return (e << 23) | (uf & 0x807fffff);
}

首先对特殊的值进行判断，如果是 $Nan$ 或者无穷大，直接返回 $uf$本身即可，对于无穷小的情况，返回乘 $2$ 后的结果并且加上符号位。对于其他情况则将阶码的值加 $1$， 然后返回就可以了。
部分题目参考这篇文章

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖