Lab1-Data Lab 深入解析

总览

题目列表

Problem-int

bitXor

要求只用“非”和“与”来表示“异或”。首先想到“异或的非=同或”：

x⊕y=x―y+xy―=x―y―⋅y―x――=(x+y―)⋅(x―+y)―=xy+x―y――

将里面的“或”变成“和”，只需利用德摩根定律：

xy+x―y――=x⋅y―⋅x―⋅y――
int bitXor(int x, int y) {
	return ~(x&y)&(~x&~y);
}

tmin

对于 32 位 int, Tmin = 0x80000000, 将 1 左移 31 位即可

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

isTmax

首先，我们知道 Tmax = 0x7FFFFFFF, 不难想到求 Tmax+1 = Tmin = 0x80000000。观察可知，~(Tmax+1) = Tmax，只需判断 ~(x+1) 与 x 是否相等即可得出结论。但是，题目要求不能用等于号，于是利用 x^x = 0 的性质进行判断，即 return !~(x+1)^x。

然而，这样是过不了的。仔细揣摩，-1 = 0xFFFFFFFF。对其进行加 1 后，该操作数会被截断，高位进位无效，使得结果为 0x00000000，每一位刚好也和 -1 的每一位互补。因此，x = -1 的情况是需要特判的。

在 C 语言中，非 0 即为真。利用 x+1=0 时结果为假这一特点，当 x = -1 时，! (x+1) = 1, 再用 ! (x+1) 与 原判式 !$ \sim $(x+1)^x 进行或运算，即 (~(x+1)^x)|!(x+1), 则该式在 x = -1 时一定为真，x != -1 时真假就一定取决于 ~(x+1)^x 。

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

allOddBits

这道题本身是很简单的，很容易想到构造一个 32 位的奇数位全为 1 的数 y = 0xAAAAAAAA，将其与 x 进行与运算，如果结果仍为 y, 则 x 的奇数位均为 1.

但要注意本实验的一个要求：

Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff.

考虑先构造 0xAA, 然后利用移位操作得到 0xAAAAAAAA。

int allOddBits(int x) {
	int y = 0xAA + (0xAA << 8);
	y = y + (y << 16);
	return !((x&y)^y);
}

negate

很基础的结论： ~x + x = -1

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

isAsciiDigit

0x30 = 0...0 00

11 0000

0x39 = 0...0 0011 1001

  1. 先检查高 26 位是否全为 0，作为条件 1

    int flag1 = !(x >> 6);

  2. 再检查中间是否为 0011，作为条件 2

    int flag2 = !(0b11 ^ (x >> 4));

  3. 最后检查末尾 4 位是否在 0000 与 1001 之间， 先得到最后四位数

    int y = x & (0xF);

  4. y 在 0 到 9 之间，则 y - 10 < 0，由于符号限制，我们通过移位后判断符号位来作为条件 3。由于不能用减法，可以通过 -x = ~x +1 达到目的

    int flag3 = (y + ~0xA + 1) >> 31;

int isAsciiDigit(int x) {
	return (!(x >> 6)) & (!(0b11 ^ (x >> 4))) & (((x & (0xF)) + ~0xA + 1) >> 31);
}

conditional

这个题很基础

F=x―z+xy

先将 x 归整化

x = !x

当 x=0 时， y = 0x00000001, 考虑 ∼y+1= 0xFFFFFFFF

当 x≠0 时， y = 0, 考虑  ∼(∼y+1)= 0xFFFFFFFF

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

isLessOrEqual

考虑 x - y

当 y 与 x 同号时，x - y 不会溢出，因此判断 x - y 的符号即可

当 y 与 x 异号时，x - y 可能会溢出，这时只分别判断 y 和 x 的符号即可

首先利用移位操作，分别得到 x, y 的符号位。

int signx = (x >> 31) & 1;
int signy = (y >> 31) & 1;

  1. 设置情况 flag1, x 负 y 正，满足情况，返回 1；x 正 y 负，返回 0

    正负 signx signy 返回值
    x 正 y 负 0 1 0
    x 负 y 正 1 0 1 
    int flag1 = signx & (!signy)

  2. 在 x, y 同号的前提下，计算 x - y，也就是 x+~y+1, 移位取符号位。

    但是要注意到：x = y 时，x+~y+1 = 0 的符号位为 0，与 x < y 时的符号位为 1 不同，因此，x = y 的情况需要特判。

    我在这里用了一种较为巧妙的办法，x≤y 等价于 x<y+1 , 使 x = y + 1 时，符号位才为 0，只需要将 x+ ~y+1 减 1 即可。

    即最终求 x+~y 的符号位。

    int e = signx ^ signy; //同号
int flag2 = ((!e) & ((x + ~y) >> 31) & 1);

int isLessOrEqual(int x, int y) {
	int signx = (x >> 31) & 1;
	int signy = (y >> 31) & 1;
	int flag1 = signx & (!signy);
	int e = signx ^ signy; //同号
	int flag2 = ((!e) & ((x + ~y) >> 31) & 1);
	return flag1 | flag2;
}

logicalNeg

当 x = 0 时，-x = 0，两者符号位相同，而当 x≠0 时，-x 与 x 的符号位显然不同，由此就可以解决本题。

令 x 与 -x 异或，则若 x = 0, 则异或后的符号位为 0，否则为 1，取符号位作为结果，则得到的结果刚好与题目中要求的返回值相反。

接下来要解决的问题就是实现 0x00000000 与 0x00000001 的相互转换，只需将其取反再加 2 即可

int logicalNeg(int x) {
	return ~((((~ x + 1) | x) >> 31) & 0x1) + 2;
}

**进一步优化：**上述做法使用了 7 个操作符，总给人一种南辕北辙的感觉。原因在于没有利用算术右移的特点

(~ x + 1) | x) >> 31;

在这一步中，如果 x≠0, 那么由于符号位为 1 ，右移后的结果便为 0x11111111, 令其加 1 ，刚好为 0；显然，当 x = 0 时，令结果加 1 ，刚好为 1 。于是，不需要“与”操作来置 0 高位，在移位完成后直接将结果加 1 ，便可过掉本题

只用了 5 个操作符

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

howManyBits

题意理解

x 为正数，以八位为例：0011 1010，需找到最高位 1，除此以外，还需一位 0 作为符号位；

x 为负数，以八位为例：1100 1001，需找到最高位 0，除此以外，还需更高一位 1 作为符号位

做法

  1. 为了统一，不妨当 x 为负数时，将其取反，如上例：$\sim $x = 0011 0110, 那么也只需要找到最高位 1 后再加一位就好，这步操作如下

    int flag = x >> 31;
x = ((~flag) & x) | (flag & (~x));

  2. 利用二分的思想，先考虑高 16 位：

    0001 1000 1100 0000 | 0000 0100 1000 0000

    将 x 右移 16 位 x = x >> 16 ：

    0000 0000 0000 0000 | 0001 1000 1100 0000

    进行规格化处理 x = !! x：

    0000 0000 0000 0000 | 0000 0000 0000 0001

    若高 16 位有 1，处理后的 x = 0x00000001。需要的位数至少为 16，引入变量 bit_16 记录该权重。怎么做呢？将处理后的 x 左移 4 位即可

    int bit_16 = (!!(x >> 16)) << 4;

  3. 如果高 16 位有 1 ，则将 x 右移 16 位，对右移后的 x 的低 16 位中的高 8 位进行同样的操作，从而二分地在 x 的高 16 位中找到最大位的 1 ；如果高 16 位没有 1 ，则 x 无需右移， 在 x 的低 16 位中的高 8 位进行同样的操作。

    由此可得右移操作：

    x = x >> bit_16;

  4. 同理，分别对高 8 位，4 位，2 位，1 位进行检查，检查后进行同样的操作。

  5. 最后将所有权重求和，便是最终结果

举例

int howManyBits(int x) {
	int flag = x >> 31;
	x = ((~flag) & x) | (flag & (~x));
	int bit_16 = (!!(x >> 16)) << 4; 
	x = x >> bit_16;
	int bit_8 = !!(x>>8)<<3;
	x = x >> bit_8;
  	int bit_4 = !!(x >> 4) << 2;
  	x = x >> bit_4;
  	int bit_2 = !!(x >> 2) << 1;
  	x = x >> bit_2;
  	int bit_1 = !!(x >> 1);
  	x = x >> bit_1;
  	int bit_0 = x;
  	return bit_16+bit_8+bit_4+bit_2+bit_1+bit_0+1;
}

Problem-float

floatScale2

先分别取符号 s，尾数 frac，和阶码 exp

unsigned s = (uf >> 31) & 0x1;
unsigned exp = (uf >> 23) & 0xFF;
unsigned frac = (uf & 0x7FFFFF);

  1. 非规格化的

    此时，exp == 0，由于此时 frac 就是尾码，直接 frac << 1 即可

  2. 规格化的

    此时，exp!=0 && ！=255，exp ++ 即可

  3. 特殊值

    根据题目要求，返回 uf

unsigned floatScale2(unsigned uf) {
	unsigned s = (uf >> 31) & 0x1;
	unsigned exp = (uf >> 23) & 0xFF;
	unsigned frac = (uf & 0x7FFFFF);
	//NaN
	if(exp == 0xFF) 
		return uf;
	//
	else if(exp == 0){
		frac <<= 1;
		return (s << 31) | (exp << 23) | frac;
	}
	//else
	exp++;
	return (s << 31) | (exp << 23) | frac;
	
}

floatFloat2Int

iEEE

与上题一样，先取符号 s，尾数 frac，和阶码 exp

unsigned s = (uf >> 31) & 0x1;
unsigned exp = (uf >> 23) & 0xFF;
unsigned frac = (uf & 0x7FFFFF);

  1. 非规格化的

    此时，exp == 0，而 E = 1 - Bias = 1 - 127 = -126, M < 1。显然，return 0

  2. 规格化的

    此时，exp!=0 && exp！=255。我们把 frac 作为基数进行修改，最后返回 frac 。首先由于这是规格化的，所以要加上开头的“1”。

    int E = exp - 127;
frac = frac | (1 << 23);
    V=(−1)s×M×2E

    • 当 E < 0 时，显然 V < 1, return 0

    • frac 为 23 位，若 E > 23, 则进行加权时，能在 frac 的末尾添加 (E - 23) 个 0

    • 若 E < 23, 则 frac 末尾的 (23 - E) 个数无法保留

    • 若 E >= 31, 显然为 infinity ，return 0x80000000u

  3. 特殊值 exp == 0xFF, return 0x80000000u

  4. 还要注意考虑负数的情况，根据 s 的值进行判断，最后利用我们前面用到的取负技巧即可。

int floatFloat2Int(unsigned uf) {
	unsigned s = (uf >> 31) & 0x1;
	unsigned exp = (uf >> 23) & 0xFF;
	unsigned frac = (uf & 0x7FFFFF);
	int E = exp - 127;
	frac = frac | (1 << 23);
	if(E < 0) return 0;
	else if(E >= 31) return 0x1 << 31;
	else{
		if(E<23) {
            frac>>=(23 - E);
        }else{
            frac <<= (E - 23);
        }
	}
	if (s)
        return ~frac + 1;
    return frac;
}

floatPower2

要做这道题，首先要导出浮点数非规格化和规格化分别表示的浮点数的范围。

  1. 非规格化的

    此时，E = 1 - Bias = 1 - 127 = -126, 而 Mmin=0.00…1=2−23, 所以非规格化浮点最小为 2−23×2−126=2−149, Mmax=2−1+2−2+⋯+2−23=1−2−23, 所以非规格化浮点最大为 2−126×(1−2−23)

  2. 规格化的

    Mmin=1, Emin=1−127=−126 所以规格化的最小为 2−126

    Mmax=1.11…11, EMINT=11111110=2127 所以规格化最大为不到 2128

可得下表：

格式 最小值 最大值
规格化 2−126 2127×(2−2−23)
非规格化 2−149 2−126×(1−2−23)

所以：

M×2−126=2x

知尾码的值是二次幂的形式，所以，尾码的值一定是通过一个“1”左移得到的。尾码各位以 2 的次幂形式的权值如下

img

设 1 左移 n 位，则 x+126 = -(23 - n)，得 n = x + 149

unsigned floatPower2(int x) {
	if(x < -149)
		return 0;
	else if(x < -126)
		return 1 << (x + 149);
	else if(x <= 127)
		return (x + 127) << 23;
	else
		return (0xFF) << 23;
}

完结纪念：

btest

总结