csapp-datalab
要求用位运算的方式实现各种运算功能，同时包括一些浮点数和整数的相互转化，难点是很多基本的运算比如加减乘除都不能用了，很多地方的实现会感觉很别扭，但确实从计算机内部角度来说会更快。
bitand
用取反和或代替与，相当于德摩根律
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~(~x | ~y);
}
getByte
取出一个word（4字节）的某个字节
先把x右移$8n(即n<<3)$位，使目标字节位于最低位，然后用0xFF取出来。
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
return 0xFF & (x >> (n << 3));
}
logisticShift
逻辑右移，和算术右移唯一的区别在于高位填充0而不是填充符号位。
~(((1 << 31) >> n) << 1)相当于造了一个高n位全是0，其他全是1的数。
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
return (x >> n) & (~(((1 << 31) >> n) << 1));
}
bitCount
挺有难度的一个，原理有点类似于分治或者二分，本质上是不断汇总子问题的解，最终求出原问题的解。
换个角度看待bitCount问题，实际上是把一个数拆成32位个1位，把每一位上的数相加得到的就是1的个数。
但是一位一位加需要加32次，那肯定会超过操作数上限。那么利用分治的思想，我可以先两位两位看，把问题这个数变成16个2位，对于每个2位，直接将这两位相加，此时，每两位上的数代表的就是这两位中1的个数。
同样，可以再把2个2位合成1个4位，也就是把这个数看成8个4位，接着看成4个8位，2个16位，最后看成1个32位，这时的x就是我们要的结果了。
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int temp, mask1, mask2, mask3, mask4, mask5;
temp = 0x55 | (0x55 << 8);
mask1 = temp | (temp << 16);
temp = 0x33 | (0x33 << 8);
mask2 = temp | (temp << 16);
temp = 0x0f | (0x0f << 8);
mask3 = temp | (temp << 16);
mask4 = 0xff | (0xff << 16);
mask5 = 0xff | (0xff << 8);
x = (x & mask1) + ((x >> 1) & mask1);
x = (x & mask2) + ((x >> 2) & mask2);
x = (x & mask3) + ((x >> 4) & mask3);
x = (x & mask4) + ((x >> 8) & mask4);
x = (x & mask5) + ((x >> 16) & mask5);
return x;
}
bang
取反，非0变成0，0变成1。
利用性质，只有0取反加1后发生溢出，结果还是0，也就是最高位是0，对于非0的数，(x | (~x + 1))的最高位一定是1。
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
return (((x | (~x + 1)) >> 31) + 1) & 1;
}
tmin
返回最小的有符号数。
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1 << 31;
}
fitsBits
判断x是否能用n位补码表示。
n位补码能表示的数范围是$[-2^{n-1}, 2^{n-1}-1]$。于是先通过sign判断x的正负，bian = n - 1。
分正负情况讨论，正数情况，!(x >> bian)说明$x<=2^{n-1}-1$。
负数情况，由于~x = -x - 1，于是!(~x >>bian)说明$-x - 1 <= 2^{n-1} - 1$即$x >= -2^{n-1}$
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
int sign = (x >> 31) & 1;
int bian = n + (~0);
return (!sign & !(x >> bian)) | (sign & !(~x >> bian));
}
divpwr2
计算$x/2^n$，向0舍入。
对于x是正数的情况直接右移就n位就可以，难点在于x是负数的情况。
因为直接右移对应的是向下舍入，但负数情况的向零舍入实际上是向上舍入。所以通过(((1 << n) + ~0) & x)把舍去的部分取出来，判断是否为0，如果非零，那么就给最后的结果补1，即从向下舍入变成向上舍入。
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int sign = (x >> 31) & 1;
int offset = ~(((1 << n) + ~0) & x) + 1;
return (x >> n) + (!!offset & sign);
}
negate
取反相反数。取反+1即可，前几个操作就一直在用的。
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
isPositive
判断x是否为正数，转化为判断是否为负数和是否为0。
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
return !((x & (1 << 31)) | (!x));
}
isLessorEqual
判断$x<=y$是否成立。
还是分类讨论，如果x为负，y为正，则成立
如果x和y同号，那么保证y-x不会溢出，判断，若y-x>=0，则成立
否则不成立
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int sig1 = (x >> 31) & 1;
int sig2 = (y >> 31) & 1;
int gap = ~x + 1 + y;
return (!(sig1 ^ sig2) & (!gap | (!((1 << 31) & gap)))) | (sig1 & !sig2);
}
ilog2
求出整数下的$log_2x$。
其实就是找到最高位的1所在的位，思路是二分查找，先找高16位，如果有1，那么继续在高16位里找，直接把低16位丢掉并给答案加16，否则到低16位里找。
思路还挺简单的，但是在只能用位运算，也不能用条件判断的情况下做就像手脚被绑住一样，还是得多动点脑筋。
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) {
int temp, sign, ans, mask_1bit, mask_2bit, mask_4bit, mask_8bit, mask_16bit;
ans = 0;
temp = 0x55 | (0x55 << 8);
mask_1bit = 0x01; //1
mask_2bit = 0x03; //2
mask_4bit = 0x0f; //4
mask_8bit = 0xff; //8
mask_16bit = 0xff | (0xff << 8); //16
temp = x & mask_16bit;
sign = !!(temp ^ x);
ans += sign << 4;
x >>= sign << 4;
temp = x & mask_8bit;
sign = !!(temp ^ x);
ans += sign << 3;
x >>= sign << 3;
temp = x & mask_4bit;
sign = !!(temp ^ x);
ans += sign << 2;
x >>= sign << 2;
temp = x & mask_2bit;
sign = !!(temp ^ x);
ans += sign << 1;
x >>= sign << 1;
temp = x & mask_1bit;
sign = !!(temp ^ x);
ans += sign;
x >>= sign;
return ans;
}
float_neg
浮点数取反。
只要判断是否为NaN，若是则直接返回，否则改变符号位后返回。
/*
* float_neg - Return bit-level equivalent of expression -f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
unsigned exp = uf << 1 >> 24;
unsigned frac = uf << 9 >> 9;
if (exp == 255 && frac != 0) return uf;
return uf ^ (1 << 31);
}
float_i2f
整数转浮点数，需要对浮点数舍入和计算规则有充分的了解。
特判x=0的情况，直接返回0。对于其他情况，$|x|$>=1，所以不需要考虑非规格化浮点数的情况。
首先记录正负情况并把x转换成正数ux(因为-2147482648会爆精度，所以ux必须是unsigned int)，求出阶数exp，满足$ux/2^{exp}$的范围在$[1,2)$之间。循环求出exp。同时这个exp也是ux最高位1的位数，所以将ux左移31-x位后，低8位就是将要被舍去的部分。
单精度浮点数精度只有23位，所以当$|x|$较大时肯定会出现舍入的情况，浮点数舍入原则是向偶数舍入。
所以要将低8位拆成tail_1bit+tail_7bit位分别做判断，当恰好为0.5时（tail_1bit = 1，tail_7bit = 0），还要判断舍入后的奇偶性，根据判断结果决定舍入。
正常来说这时候第24位一定是1，并且这个1可以被省去（根据浮点数计算方式）。但是有一个非常细节的地方需要判断，考虑这种非常极端的情况，比如x=2147483647，由于舍入要加一，结果导致这加的一位一直被进位到第25位上。但第25位已经属于阶码位了，这肯定是不允许的。
好在一旦发生这种情况，这意味着低24位一定全是0（只有以上这种不断进位的情况可能导致），否则第24位一定为1。所以只要再把这个数右移一位，然后令阶码+1。这样一来还能保证第24位仍然为1。
而判断这种情况只要判断第24位是否为1，也就是(ux & (1 << 23))是否成立。
最后把符号位和阶码位填上，就得到答案了。
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
unsigned ux, sig = (x >> 31) & 1;
unsigned exp = 0, t;
unsigned tail_1bit, tail_7bit;
if (x == 0) return 0;
if (x < 0) ux = -x;
else ux = x;
t = ux;
while(t) {
exp++;
t /= 2;
}
exp--;
ux <<= 31 - exp;
tail_1bit = ux & 0x80;
tail_7bit = ux & 0x7f;
ux >>= 8;
if (tail_1bit && tail_7bit) ux++;
else if (tail_1bit && !tail_7bit && (ux & 1)) ux++;
if (ux & (1 << 23)) ux ^= (1 << 23);
else exp++;
exp += 127;
ux |= sig << 31;
ux |= exp << 23;
return ux;
}
float_twice
浮点数乘二。
对于NaN，无穷大和0，直接返回。
对于规格化浮点数（阶码非0），阶码加一后返回。
对于非规格化浮点数的情况，如果存储位$frac<=4194303=2^{22}-1$，也就是保证乘2后还是一个非规格化浮点数，那么存储位乘二后返回。
否则一定会从一个非规格化浮点数转换成规格化浮点数，因为只需要乘二，说明阶码一定是从0变成1，但这两种情况所对应的实际阶数是一样的，都是E = 1-bias = -126，所以只要保证存储位仍然相等就可以了。区别就在于规格化浮点数最后计算时要加1，那么在存储时减1，反应在存储位上的方法则是减去$8388608=2^{23}$。
/*
*
* float_twice - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representation of
* single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_twice(unsigned uf) {
unsigned sign = (uf >> 31) & 1, exp = (uf >> 23) & 0xff, frac = uf << 9 >> 9;
unsigned ans = 0;
if (exp == 255 || (exp == 0 && frac == 0)) return uf;
if (exp != 0) {
exp ++;
ans = sign << 31 | exp << 23 | frac;
return ans;
}
if (frac <= 4194303) frac *= 2;
else {
exp++;
frac = frac * 2 - 8388608;
}
ans = sign << 31 | exp << 23 | frac;
return ans;
}