CSAPP Data Lab

bitXor

题目

描述：仅使用~和&实现^操作。

允许使用的操作符：~ &

允许使用的操作符最大数量：14

实现

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

解析

有：

1. x ^ y = (x | y) & (~(x & y))

2. x | y = ~((~x) & (~y))

故：

x ^ y = (~((~x) & (~y))) & (~(x & y))

tmin

题目

描述：返回二进制补码整数的最小值。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：4

实现

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

解析

INT_MIN为0b10[31]，故将1左移31位即可

isTmax

题目

描述：判断输入参数是否是二进制补码整数所能表示的最大值，是则返回1，否则返回0。

允许使用的操作符：！ ~ & ^ | +

允许使用的操作符最大数量：10

实现

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

解析

INT_MAX为0b01[31]，可知~INT_MAX = INT_MAX + 1。下面证明除了INT_MAX和0b1[32]外无其他数使得~x = x + 1：

对于任何a，除了0b1[32]外，均有a = A01[n]。此时~a = ~A10[n]，a + 1 = A10[n]，若希望~a = a + 1，要求A = ~A，这只有当A为空的情况下成立。

同时，~0b1[32] = 0b0[32]，0b1[32] + 1 = 0b0[32]，同样成立。

因此，本题实质上进行如下判断：

1. x + 1 == ~x，当(x + 1) ^ ~x为零时成立

2. x != 0b0[32]，当~x不为零时成立。

allOddBits

题目

描述：判断输入参数的所有奇数位上的数值是否为1，下标从0开始。是则返回1，否则返回0。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：12

实现

int allOddBits(int x) {
	x = x >> 1;
	x = x & (x >> 2);
	x = x & (x >> 4);
	x = x & (x >> 8);
	x = x & (x >> 16);
	return x & 1;
}

解析

其实本题最简单的思路是构造mask = 0xAAAAAAAA，判断x & mask是否等于mask即可。

目前采用的思路是遍历。利用&操作符的x & (y & z) = x & y & z的性质逐层计算，最终获得结果。原理示意图如下图：

negate

题目

描述：返回输入参数的相反数。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：5

实现

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

解析

x + (-x) = 0b0[32] = 0b1[32] + 0b1

所以有：

(-x) = 0b1[32] + 0b1 - x = (~x) + 0b1

isAsciiDigit

题目

描述：返回输入参数的值是否在[0x30, 0x39]区间内，是则返回1，否则返回0。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：15

实现

int isAsciiDigit(int x) {
	return !((x & (~0x3f)) | ((x & 0x30) ^ 0x30) |
		((!!(x & 0x8)) & (!!((x & 0xe) ^ 0x8))));
}

解析

经分析，有如下条件：

1. x <= 0x3f，故有x & (~0x3f)为0

2. x >= 0x30，故有(x & 0x30) ^ 0x30为0

3. x <= 0x39，根据其对应二进制特征，可分为以下两类：

   • 0x30 <= x <= 0x37，其特征为后4个比特为0b0xxx，故有x & 0x8为0

   • 0x38 <= x <= 0x39，其特征为后4个比特为0b100x，故有(x & 0xe) ^ 0x8为0

   上述两项只要有一项为0即可，故采用&进行连接。为了保证二者均不为0时结果也不为0，使用!!对剩下的位数进行对齐。

conditional

题目

描述：要求函数行为与x ? y : z一致。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：16

实现

int conditional(int x, int y, int z) {
	x = !x;
	x = x | (x << 1);
	x = x | (x << 2);
	x = x | (x << 4);
	x = x | (x << 8);
	x = x | (x << 16);
	return ((~x) & y) | (x & z);
}

解析

做出如下mask，当x = 0时，mask = 0b1[32]；当x != 0时，mask = 0b0[32]。之后对输入进行&操作即可。

isLessOrEqual

题目

描述：判断是否有x <= y，是则返回1，否则返回0。

允许使用的操作符：！ ~ & ^ | + << >>

允许使用的操作符最大数量：24

实现

int isLessOrEqual(int x, int y) {
	return !((((~x) + 1 + y) & (1 << 31)));
}

解析

进行如下判断：(-x) + y >= 0。又有(-x) = ~x + 0b1。故进行计算后判断符号位即可。

logicalNeg

题目

描述：行为应与!x相同。

允许使用的操作符：~ & ^ | + << >>

允许使用的操作符最大数量：12

实现

int logicalNeg(int x) {
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
	return (~x) & 1;
}

解析

制作如下mask：x = 0时，mask = 0b0[32]，x != 0时，mask = 0b1[32]。最后按位取反并取最后一位即可。

howManyBits

题目

描述：返回表示x需要的最少位数。

允许使用的操作符：! ~ & ^ | + << >>

允许使用的操作符最大数量：90

实现

int howManyBits(int x) {
	int mark2;
	int mark4;
	int mark8;
	int mark16;
	int mark32;

	mark2 = 0x55;
	mark2 |= mark2 << 8;
	mark2 |= mark2 << 16;

	mark4 = 0x33;
	mark4 |= mark4 << 8;
	mark4 |= mark4 << 16;

	mark8 = 0xf;
	mark8 |= mark8 << 8;
	mark8 |= mark8 << 16;

	mark16 = 0xff;
	mark16 |= mark16 << 16;

	mark32 = 0xff;
	mark32 |= mark32 << 8;

	// 将负数取反，正数不变
	x = x ^ (x >> 31);

	// 将x转化为0b0[n]1[32-n]的形式
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);

	// 对1的个数进行求和
	x = (x & mark2) + ((x >> 1) & mark2);
	x = (x & mark4) + ((x >> 2) & mark4);
	x = (x & mark8) + ((x >> 4) & mark8);
	x = (x & mark16) + ((x >> 8) & mark16);
	x = (x & mark32) + ((x >> 16) & mark32);

	// 加上符号位
	return x + 1;
}

解析

本次实验中最难的题，根据题意，其实际上是在找去除多余符号位后的整数补码表示位数。

首先，为了简化情况，观察到howManyBits(x) = howManyBits(~x)，于是选择将负数取反。这一步中涉及一些位运算技巧：

1. 对0的`^`相当于取反，对1的`^`则保持原值。

2. `int`的右移为算数右移，右移31位的结果相当于获得一个由符号位填充的`mask`。

之后，为了便于计算，将x转化为0b0[n]1[32-n]的形式（之前的负数要取反也是为了统一该步的操作）。

接下来，使用mask和移位操作，统计x中1的个数，其过程示意图如下图：

将得到的x加上一位符号位获得最终结果。

floatScale2

题目

描述：返回2 * x的二进制表示，对于INF和NaN原样返回。

允许使用的操作符：任意int/unsigned的算数运算符、||、&&运算符和if、while关键字。

允许使用的操作符最大数量：30

实现

unsigned floatScale2(unsigned uf) {
	unsigned s = uf >> 31;
	unsigned exp = (uf >> 23) & 0xff;
	unsigned frac = uf & 0x7fffff;

	if(exp == 0xff) {
		return uf;
	}

	if(exp == 0) {
		frac <<= 1;
	} else {
		exp += 1;

		if(exp == 0xff) {
			frac = 0;
		}
	}
	return (s << 31) | (exp << 23) | frac;
}

解析

根据浮点数的结构，将其拆分成s、exp和frac。

1. 对于NaN和INF，直接返回原数据。

2. 对于非规格化数，将frac右移一位即可。注意，此时非规格化数可能会转化成规格化数，但转化后的结果为exp = 1和frac & ~0x800000，在组装成为浮点数后的结果与直接进行组装相同，故不需要进行特殊处理。

3. 对于规格化数，需要将exp加1。但在操作后有可能导致溢出，故需要将frac置0，将结果设为INF而不是NaN。

floatFloat2Int

题目

描述：返回(int)x的返回值，对于INF和NaN和溢出值返回0x80000000。

允许使用的操作符：任意int/unsigned的算数运算符、||、&&运算符和if、while关键字。

允许使用的操作符最大数量：30

实现

int floatFloat2Int(unsigned uf) {
	unsigned s = uf >> 31;
	unsigned exp = (uf >> 23) & 0xff;
	unsigned frac = uf & 0x7fffff;

	frac |= 0x800000;

	if(exp <= 0x96) {
		if(exp < 0x7f) {
			return 0;
		}

		frac >>= 0x96 - exp;
	} else {
		if(exp >= 0x9e) {
			return 0x80000000;
		}

		frac <<= exp - 0x96;
	}
	return s ? (~frac) + 1 : frac;
}

解析

根据浮点数的结构，将其拆分成s、exp和frac。

1. 对于INF和NaN，直接返回0x80000000。

2. 对于非规格化数，直接返回0。

3. 对于规格化数，需要现根据exp判断其是否溢出或为0。注意，由于我们将目前的计算视为正数，故原则上需要特别INT_MIN，但应为本次溢出返回值即为INT_MIN，因此可以两者进行合并处理，只要发生正数溢出便返回INT_MIN。

4. 根据符号位将其转化成为补码。

代码中各个数值的出现的原因：

1. 0x7f：即加上偏置值后exp实际为0时的exp值。若exp小于该值，则该浮点数不存在整数部分。

2. 0x96：因为在取frac的时候是整数形式，因此实际上暗中给其加上了一层偏置，大小为frac小数部分位数23。故有0x7f + 0x17 = 0x96。若exp小于该值，则frac需要右移，否则需要左移。

3. 0x9e：对于规格化整数，在其frac中的整数部分的1到达符号位时发生溢出，此时右移位数为31。固有0x7f + 0x1f = 0x9e。若exp小于该值，则规格化数不会溢出，否则发生溢出。

floatFloat2Int

题目

描述：返回2.0 ^ x的二进制表示，如果结果过大则返回+INF

允许使用的操作符：任意int/unsigned的算数运算符、||、&&运算符和if、while关键字。

允许使用的操作符最大数量：30

实现

unsigned floatPower2(int x) {
	if(x >= 128) {
		return 0x7f800000;
	}

	if(x > -127) {
		return (0x7f + x) << 23;
	}

	if(x < -150) {
		return 0;
	}

	return 0x800000 >> (-x - 126);
}

解析

1. 当x大于等于128时，超过浮点数最大值，发生溢出，返回+INF。

2. 当x大于-127小于128时，是规格化数，只需要处理exp部分。

3. 当x小于-150时（-150 = -127 + -23），超出浮点数精度，返回0。

4. 否则，为非规格化数，只需要处理frac部分。