Solution

bitXor

限定~，&运算,求a和b的^
思路是先把所有相同的位取出来
分为相同的 $0$ 和 $1$
考虑一下 $1$ 就是 $a\&b$
同理 $0$ 就是把 $a$ 和 $b$ 取反的情况

最后取出来之后没有和 $0$ 的或操作
就按照逻辑门原理构造一个就行

int bitXor(int x, int y) {
    int allOneBits = x & y;
    int allZeroBits = ~x & ~y;
    return ~0 & ~allOneBits & ~allZeroBits;
}

tmin

题意是返回二进制下最小整数
这个很简单，直接返回 INT_MIN即可

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

isTmax

想法是类似上面一题，外面套个 $!$ 判断一下就行
INT_MAX用 INT_MIN取反来构造
~~但是<<不能用，坏~~

但是看到这里可以用加法，直接乱搞到一个能判断的数就行
令 $t=x+x+1$ ，取个反就是 $0$ 。这里要考虑溢出，特判一下 $-1$
最后外面用德摩根定律套一层

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

allOddBits

刚开始还在想性质，后面直接放弃了，直接暴力破解了
&一下所有的奇数位，判断是否都在

int allOddBits(int x) {
    int mask = 0xAA | 0xAA << 8 | 0xAA << 16 | 0xAA << 24;
    return !(x & mask ^ mask);
}

negate

考察的知识点：~ $x=-(x+1)$
这个用补码相关知识很容易得到

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

isAsciiDigit

直接硬算了
把条件转换成注释里的写的表达式，然后用 $1<<31$ 来判负
注意这里不能把式子设计成 $\leq0$ ，因为还要花额外的操作符来判 $0$
拆了括号优化了一下左边的式子，少了一个操作符
最后还是德摩格定律

int isAsciiDigit(int x) {
    // x - 0x2F > 0 && x - 0x3A < 0
    // negate(x) + 0x2F < 0 && x + negate(0x3A) < 0
    return !(!(~x + 0x30 & 1 << 31) | !((x + (~0x3A + 1) & 1 << 31)));
}

conditional

思路是实现一个函数：

f(x)=\begin{cases} 0xffffffff&\text{if }x\neq0\\ 0&\text{if }x=0 \end{cases}

因为提供了+操作，直接&完加起来

一个很简单的映射是!运算提供的

!x=\begin{cases} 1&\text{if }x=0\\ 0&\text{if }x\neq0 \end{cases}

加一个偏置再取反就好了，得到：

!x-1=\begin{cases} 0&\text{if }x=0\\ -1&\text{if }x\neq0 \end{cases}

而-1的二进制位表示就是0xffffffff，而且其实只要考虑y，z直接取反就可以
但是为了考虑所有映射的唯一性，还是要把函数写出来分析

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

isLessOrEqual

前面先特判一下符号位防止溢出
这里判断符号了所以可以直接对 $x,y$ 进行位移运算
后面仿照isAsciiDigit判断一下零和负数就行
懒得判零也可以判 $y-1-x$ 负数

int isLessOrEqual(int x, int y) {
    int xSign = x >> 31 & 1, ySign = y >> 31 & 1;
    int t = xSign + ~ySign + ~1 + 2;
    int xlty = !t;
    int xgty = !(t + 2);
    int xSuby = x + ~y + 1;
    int zeroFlag = !xSuby;
    int negFlag = xSuby >> 31 & 1;
    return (!xgty) & (xlty | zeroFlag | negFlag);
}

logicalNeg

不是 $0$ 的话， $x$ 和 $-x$ 里面必存在一个符号为是 $1$ 的数
对其进行 $>>31$ 必得到 $-1$ ，否则如果 $x$ 是 $0$ 的话就是 $0$ ，再加 $1$ 就行

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

howManyBits

首先肯定要一个符号位剩下就是 $|x|$ 的二进制表示的最高位数了 $|x|$ 的只要通过 $x>>31$ 导致的所有位全 $0$ 或 $1$ ，稍微乱搞一下就行了然后是求最高位数，一个一个枚举位数的话应该会超Max ops，考虑二进制优化有点像背包问题的二进制优化和树状数组上二分查找，最高位能填就填，最后得到的位数是唯一的这里从 $16$ 到 $1$ 枚举第 $1$ 到 $31$ 位，最后再判断一下第 $0$ 位

小技巧：
!!可以实现把非 $0$ 映射到 $1$ ， $0$ 映射到 $0$ ，再 $<<$ 相应位数就可以得出 $x$ 要 $>>$ 的位数

int howManyBits(int x) {
    int b0, b1, b2, b4, b8, b16;

    // if x is negative, then ~x = -x - 1
    int sign = x >> 31;
    x = (sign & ~x) | (~sign & x);

    x = x >> ((b16 = !!(x >> 16) << 4));
    x = x >> ((b8 = !!(x >> 8) << 3));
    x = x >> ((b4 = !!(x >> 4) << 2));
    x = x >> ((b2 = !!(x >> 2) << 1));
    x = x >> ((b1 = !!(x >> 1) << 0));
    b0 = x;
    return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

floatScale2

思路是先把符号位、阶码、尾数分别取出来
然后分情况讨论：

规格化的值：相当于阶码 $+1$
非规格化的值：不能操作阶码，让尾数 $<<1$
特殊值：不作任何操作

unsigned floatScale2(unsigned uf) {
    unsigned sign = uf & 0x80000000;
    unsigned exp = uf & 0x7F800000;
    unsigned frac = uf & 0x7FFFFF;

    if (exp == 0x7F800000) {
        return uf;
    } else if (exp == 0) {
        return sign | (frac << 1);
    }
    return uf + 0x800000;
}

floatFloat2Int

这题挺麻烦的， $E>31$ 居然也要特判。同先把符号位、阶码、尾数分别取出来。这里把阶码转移到低位上，方便后续计算。先判断一下阶码是不是特殊值，然后减掉偏置把 $E$ 算出来。这里 $E>31$ 也要特判，超 i32了，选择放在减掉偏置之后判断，代码好看一点。后面把 $E$ 减掉本来尾数的长度 $23$ ，设置一下小数点的初始位置并考虑小数点前的 $1$ 的存在性。最后再特判一下 $E<-23$ 防止可能的循环 $>>$ 导致奇奇怪怪的问题就行了。

本来还要考虑负数向零取整，这里直接用正数 $>>$ 操作默认向下取整，最后返回的时候考虑符号就行了。

int floatFloat2Int(unsigned uf) {
    unsigned sign = uf & 0x80000000;
    unsigned exp = uf >> 23 & 0xFF;
    int E;
    int frac = uf & 0x7FFFFF;

    if (exp == 0xFF) {
        return 0x80000000;
    }

    E = (exp ? exp - 127 : -126) - 23;
    frac |= (!!exp) << 23;
    frac = E >= 0 ? E > 8 ? 0x80000000 : frac << E : E < -23 ? 0 : frac >> -E;
    return sign ? -frac : frac;
}

floatPower2

这题意外地水，先特判一下，两种情况：

$x<-126$ ，爆下限了，直接返回 $0$
$x>127$ ，爆上限了，直接范围 $+INF$

否则在能正常表示的范围内，考虑一下特殊情况：
当 $x=0$ 时，表示的是 $1.0$ ，即 $0x00000000$
可以看到这个表示非常的反直觉，按理来说 $1.0$ 的表示应该很简单来说，原因是偏置的存在
于是我们不妨把偏置先拿掉，最后再加上，这样的话 $1.0$ 的表示就是 $0x00000000$

x	去掉偏置表示 $2.0^x$ （假设这里阶数表示的是有符号数）
-2	0x7F700000
-1	0x7F800000
0	0x00000000
1	0x00800000
2	0x00900000

这样看起来很复杂，其实表达的意思就是因为是 $2.0$ 的幂，原始的小数位（既尾数）什么都没有，只需要考虑阶数就行，而 $x$ 已经确定在阶数范围内了，所以不用担心溢出，直接加上偏置（这里交给内部计算处理了）再 $<<23$ 。

unsigned floatPower2(int x) {
    if (x < -126) {
        return 0;
    } else if (x > 127) {
        return 0x7F800000;
    }
    return (x + 127) << 23;
}

总结：

题目对于一些细节的考察设置得很好，在一定已有知识和技巧的基础上有扩展也有深入，深受启发。同时熟悉了位运算的各种操作，修正了许多之前错误的认知。运算符的限制有助于锻炼代码能力，在未来的coding过程中更好使用位运算的维护代码简洁性 $\xcancel{\text{（虽然可读性大大降低了）}}$ 。另外，题目中说的循环好像一点用都没有啊。

csapp:datalab