CSAPP Lab1

CSAPP

bits.c

在bits.c中做题目
使用make clean和make进行编译
调用./btest -f funcName测试funcName函数的结果，可以在代码中中插入printf输出中间结果，但是要记得最后删掉
调用./dlc bits.c查看是否使用了非法或过多的运算符
重复以上步骤，最后可以直接运行./btest输出最后结果。

得分图

本地的fitsBits的Check可能有问题，没法过。

补充一个位运算优先级图。

bitAnd

x&y using only ~ and |
~x与~y中同时为$0$的位即为x&y中为$1$的位，或起来取反即可。

int bitAnd(int x, int y) {
    return ~(~x|~y);
}

getByte

Extract byte n from word x
用0xFF分别与x,x>>8,x>>16,x>>24即可。

int getByte(int x, int n) {
    return 0xFF&(x>>(n<<3));
}

logicalShift

shift x to the right by n, using a logical shift
简单的想法是x>>n与一个高$n$位为$0$其余全$1$的数$x$，$x$取反就是$\begin{matrix}\underbrace{111}..000\\n个1\ \ \ \ \ \ \ \ \ \end{matrix}$，用$1<<31$就可以算术右移$n$位得到高$n$位的$1$，然后再左移$1$位即可。

令一个想法是，$111...000$就是$0xFFFFFFFF$左移$32-n$位。
有三个问题及前两个的解决方法依次是：
1. $n=0$时$位移量=w=32$，先左移$31$位再右移$n$位，最后再左移$1$位，避免最高位的$1$丢失。
2. $0xFFFFFFFF$右移时是逻辑右移，要转成int或写成$-1$才是算术右移，才不丢失最高位的$1$，但是不能有 类型转换 和 负号及十进制数。
所以必须是恰好左移$32-n$位，解决方法是对$31-n$二进制拆分（$31-n$的二进制表示比$32-n$更容易知道），写成$\log n$个与和右移，最后再左移$1$位。这样改完后代码：(x>>n)&~(0xFFFFFFFF<<(!(n&16)<<4)<<(!(n&8)<<3)<<(!(n&4)<<2)<<(!(n&2)<<1)<<(!(n&1))<<1);。
3. 常数只能是$0x0\sim 0xFF$（不过可以构造出来），以及运算符数超过了$20$。所以这个方法不行。

int logicalShift(int x, int n) {
    return (x>>n)&~(1<<31>>n<<1);
}

bitCount

returns count of number of 1s in word
做法是整体的分治。令$v_1=01\ 01\ 01\ 01...,v_2=0011\ 0011...,v_3=0000\ 1111...$直到$v_5=0000\ 0000\ 0000\ 0000\ 1111\ 1111\ 1111\ 1111$。
先计算每两位中$1$的个数$n_2$，即为$n_2=(x\&v_1)+(x>>1\&v_1)$，每两位的$1$的个数会存在这两位中。
再计算每四位中$1$的个数，即$n_4=(n_2\&v_2)+(n_2>>2\&v_2)$，每四位的$1$的个数会存在这四位中。
同理，每八位中的$1$为$n_8=(n_4\&v_3)+(n_4>>4\&v_3)$，十六位为$n_{16}=(n_8\&v_4)+(n_8>>8\&v_4)$，三十二位为$n_{32}=(n_{16}\&v_5)+(n_{16}>>16\&v_5)$，即为答案。

有个细节是，计算$n_8$时$n_4+(n_4>>4)$得到的每八位$1$的个数不会超过$2^4=16$，即不会溢出$v_3$中限制的$4$位，所以可以先加起来再一起$\&$减少一次操作数。$n_{16},n_{32}$同理。

还有限制常数最多为八位，所以需先构造$v_1'=01010101|(01010101<<8)=0x55|(0x55<<8),v_1=v_1'|(v_1'<<16)$，以及$v_2'=00110011|(00110011<<8)=0x33|(0x33<<8),v_2=v_2'|(v_2'<<16)$，以及$v_3'=0xF|(0xF<<8),v_3=v_3'|(v_3'<<16)$。

int bitCount(int x) {
    int tv1=0x55|(0x55<<8),v1=tv1|(tv1<<16);
    int tv2=0x33|(0x33<<8),v2=tv2|(tv2<<16);
    int tv3=0xF|(0xF<<8),v3=tv3|(tv3<<16);
    int v4=0xFF|(0xFF<<16);
    int v5=0xFF|(0xFF<<8);
    int res=(x&v1)+(x>>1&v1);
    res=(res&v2)+(res>>2&v2);
    res=(res+(res>>4))&v3;
    res=(res+(res>>8))&v4;
    res=(res+(res>>16))&v5;
    return res;
}

bang

Compute !x without using !
结果为$1$当且仅当x=0，所以问题在于怎么将一个数的$1$放到个位上。有个位的$1$后，取反与$1$就可以了。

类似bitCount的分治，用x|=x>>1求出两两分组后的两位中是否有$1$并放到低位上，然后x|=x>>2，求出四个一组的数中是否有$1$并放到低位上...直到x|=x>>16。

从x|=x>>16开始也可，先将$1$汇聚到低$16$位上，再x|=x>>8可以将$1$汇聚到低$8$位上，...直到x|=x>>1。

还有种方法是，利用$0$和$-0$（~x+1）的符号位均为$0$，而其他数中有一个$1$的性质，取出这个$0$。即：~((x|(~x+1))>>31)&1。

int bang(int x) {
    return ~((x|(~x+1))>>31)&1;
//Another sol:
    // x|=x>>1;
    // x|=x>>2;
    // x|=x>>4;
    // x|=x>>8;
    // x|=x>>16;
    // return ~x&1;
}

tmin

return minimum two's complement integer
即1<<31。

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

fitsBits

return 1 if x can be represented as an n-bit, two's complement integer.
若$-2^n\leq x\lt 2^n$，则$x$若为正数，则高$32-n$位均为$0$，若为负数，则高$32-n$位均为$1$。所以$x$左移$32-n$位后再右移$32-n$位应不变。否则$x$越界则$x$数值会改变。
注意32-n=32+(~n+1)，a==b可以改写为!(a^b)。

int fitsBits(int x, int n) {
    int delta=33+(~n);
    return !(x^(x<<delta>>delta));
}

divpwr2

Compute x/(2^n), for 0 <= n <= 30 (Round toward zero)
$x$为正数则为$x>>n$，为负数则为$x+(1<<n)-1>>n$。
将$1$替换成$x$的符号位即可。注意若$x$为负则$x>>31=-1$，提取符号位需要$\&1$，但可以直接作为减$1$。

int divpwr2(int x, int n) {
    int sign=x>>31;
    return (x+((sign&1)<<n)+sign)>>n;
}

negate

return -x
~x+1。

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

isPositive

return 1 if x > 0, return 0 otherwise
需要判$0$，而$-0$的符号位不变，所以同divpwr2中用$(-x>>31)\&1$提取$-x$的符号位即可。但有个问题是$-TMIN=TMIN$，所以还要特判$TMIN$否则不对。
更简单的是直接求符号位，然后$\&(!!x)$来特判$0$。

int isPositive(int x) {
    return (!(x>>31))&(!!x);
}

isLessOrEqual

if x <= y then return 1, else return 0
如果不溢出就是isPositiveOrZero(y-x)即!((y-x)>>31&1)。注意到y-x溢出只发生在$x,y$异号，而异号可以直接判断大小。所以先求一下$x,y$的符号位判断是否溢出即可。

int isLessOrEqual(int x, int y) {
    int sx=x>>31&1, sy=y>>31&1;
    return ((!sy)&sx)|(!(sy^sx)&!((y+~x+1)>>31&1));
}

ilog2

return floor(log base 2 of x), where x > 0
即求最高位的$1$。最简单的方法是再最高位右边全填上$1$，再用bitCount-1。
填充$1$类似bang，x|=x>>16,x|=x>>8,...,x|=x>>1，从高位传下来即可。也同bang先x|=x>>1最后x|=x>>16都可。

还有种方法是，先求出高$16$位是否有$1$，有就加$2^{16}$；然后再求当前$16$位中高$8$位是否有$1$，有就加$2^8$...直到最后一位。

int ilog2(int x) {
    int tv1=0x55|(0x55<<8),v1=tv1|(tv1<<16);
    int tv2=0x33|(0x33<<8),v2=tv2|(tv2<<16);
    int tv3=0xF|(0xF<<8),v3=tv3|(tv3<<16);
    int v4=0xFF|(0xFF<<16);
    int v5=0xFF|(0xFF<<8);
    int res;//鍙よ€佺殑csapp鏍囧噯瑕佹眰C涓嚱鏁板０鏄庡繀椤昏鍦ㄦ渶鍓嶉潰
    x=x|(x>>16), x=x|(x>>8), x=x|(x>>4), x=x|(x>>2), x=x|(x>>1);
    res=(x&v1)+(x>>1&v1);
    res=(res&v2)+(res>>2&v2);
    res=(res+(res>>4))&v3;
    res=(res+(res>>8))&v4;
    res=(res+(res>>16))&v5;
    return res+~1+1;
}

float_neg

Return bit-level equivalent of expression -f for floating point argument f.
实数取反，取反符号位即可。要特判NaN。

unsigned float_neg(unsigned x) {
    if((x&0x7FFFFFFF)>0x7F800000) return x;
    return x^0x80000000;
}

float_i2f

Return bit-level equivalent of expression (float) x
若$x$为负数，则先将$x$取反；为$0$可直接特判。
设最高位的$1$为第$i$位，则浮点数的阶码$E$为$i+Bias=i+127$，小数子段$f$则为低$i$位（如果小于$23$位则后面补$0$，大于$23$位则舍弃并进位，注意是向偶数舍入！）。最后再加上符号位。
具体：
用前面方法或循环找到最高位的$1$，设其距第$31$位距离为$d$，则直接将ux=(unsigned)x左移$d+1$位，使小数子段确定为$ux$的$31\sim 9$位，舍弃位为$8\sim 0$位。
偶数舍入两种情况：1. 舍弃的$9$位大于$2^9$，即ux&0x1FF>0x100；
2. 有效位和最高舍弃位均为$1$，即第$9$位和第$8$位均为$1$，即ux&0x300==0x300或ux&0x3FF>=0x300。（我怎么总是忘了位是从$0$开始标号）

最高符号位，加上从$23$位开始的$低位个数+127$，最后加上小数子段$ux>>9$和进位即为答案。

unsigned float_i2f(int x) {
    unsigned ux=x,sign=ux>>31,carry=0; int d=0;
    if(!x) return 0;
    if(sign) x=~x+1, ux=x;
    while(!(x&0x80000000)) x<<=1, ++d;
    ux<<=d+1;
    carry=((ux&0x1FF)>0x100)|((ux&0x300)==0x300);
    return (sign<<31)+((31-d+127)<<23)+(ux>>9)+carry;
}

float_twice

Return bit-level equivalent of expression 2*f for floating point argument f.
如果是规格化数，直接阶码$+1$（直接加0x800000）；
如果是非规格化数，只需将$x$左移$1$位（注意符号位）。
特殊值则直接返回。

unsigned float_twice(unsigned x) {
    if((x&0x7F800000)==0x7F800000) return x;
    else if(!(x&0x7F800000)) return (x<<1)|(x&0x80000000);
    else return x+0x800000;
}