Data Lab

Integer

BitXor

用与非实现异或

容易知道 (a & ~b) | (b & ~a)可以实现异或，再通过德摩根律就得到答案

1
2
3

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

Tmin

即求二进制补码最小值 100...00，把 1左移 31 位即可

1
2
3

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

isTmax

判断一个数是不是 $ Tmax$

注意到 $Tmax+1=Tmin$ 并且它们每一位恰好是反的，将其中一个按位取反再异或，将这个结果取否定即可，但是需要排除一下 $-1$ ，使用 !!(x+1)，这个表达式只会排除 $-1$

1
2
3

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

allOddBits

判断一个二进制数奇数位是不是都是1

构造一个掩码 mask=0xAAAAAAAA ，和 $x$ 按位与提取出 $x$ 的奇数位，提取出后只有和 $mask$ 一样才能返回 $1$，所以进行异或运算后取否定即可得到结果

这也提供了一种判断 $a$ 和 $b$ 是否相等的方法 !(a ^ b)

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

negate

求相反数

1
2
3

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

isAsciiDigit

判断一个数是不是 Ascii 数字

范围是 0x30~0x39

发现一定由第 5 到 8 位一定是 3，采用 !((x >> 4) ^ 3)判断

第 1 到 4 位分开讨论，提取第 4 位，如果是 0 说明 x 在 0~7 之间

提取 2，3，4 位（&14）如果是 8 说明 x 是 8 或 9

1
2
3

int isAsciiDigit(int x) {
  return ( (!((x & 8) ^ 0)) | (!((x & 14) ^ 8)) ) & (!((x >> 4) ^ 3));
}

conditional

实现三目运算符

为准确提取 $y$ 或 $z$ 首先需要实现 $x$ 非零时返回 $0xFFFFFFFF$，为零时返回 $0x00000000$

注意到之前可以判断是否相等，首先想到判断和 $0$ 是否相等 !(x ^ 0)

这时很好的区分了零和非零，为零返回 $0x00000001$ ，非零返回 $0x00000000$

不能使用减号，不如考虑取反加 $1$ ，为零返回 $0xFFFFFFFF$ ，非零返回 $0x00000000$ 恰好再取一次反得到结果

此时 $x$ 为真提取 $y$，否则提取 $z$ 即可

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

isLessOrEqual

判断是否小于等于

简单来说直接求 $y-x=y+(-x)$ 再判断符号位是什么即可

但是异号一定会溢出，所以只能同号这样求，异号时 $x$ 负 $y$ 正一定成立

int isLessOrEqual(int x, int y) {
	int xOp, yOp;
	xOp = x >> 31;
    yOp = y >> 31;
    return (xOp & !yOp) |                       // x负y正
           (~(xOp ^ yOp) &                     // 符号相同
            !((y + (~x + 1)) >> 31));          // 且y-x>=0
}

logicalNeg

实现逻辑否

也就是为零时逻辑否是 $0x00000001$ ，非零时逻辑否是 $0x00000000$

注意到 $0=-0$ ，其他数取相反数符号位几乎都会改变

但是 $Tmin=-Tmin$ 但注意到它和 $0$ 的最高位不同

采用 x|(~x+1) 得到只有 $0$ 最高位是 $0$，做算术右移再加 $1$ 即可

1
2
3

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

howManyBits

求将 $x$ 表示为二进制补码所需要的最小位

不难发现排开符号位只需要找到第一个 $1$ 所在的位置序号（最低有效位）加上 $1$ （表示符号）即可，不妨只考虑正数或者说把所有数转化为正数再考虑

sign = x >> 31

x = (sign & ~x) | (~sign & x);

做个映射，前 $16$ 位如果有 $1$，位数二进制表示一定是 $0b1XXXXX$

往后 $8$ 位如果有 $1$，位数二进制表示一定是 $0bX1XXXX$

往后 $4$ 位如果有 $1$，位数二进制表示一定是 $0bXX1XXX$

往后 $2$ 位如果有 $1$，位数二进制表示一定是 $0bXXX1XX$

倒数第二位如果是 $1$，位数二进制表示一定是 $0bXXXX1X$

最后一位如果是 $1$，位数二进制表示一定是 $0bXXXXX1$

类似二分查找，统一化为

1
2
3

// 前k位是否存在1，有就右移x
    b_k = (!!(x >> k)) << f(k)-1;
    x = x >> b_k;

最终代码如下

int howManyBits(int x) {
	int b16, b8, b4, b2, b1, b0;
    int sign = x >> 31;
    x = (sign & ~x) | (~sign & x);	// x转化为正数
    
    // 前16位是否存在1，有就右移x
    b16 = (!!(x >> 16)) << 4;
    x = x >> b16;
    // 高8位是否存在1，有就右移x
    b8 = (!!(x >> 8)) << 3;
    x = x >> b8;
    // 高4位是否存在1，有就右移x
    b4 = (!!(x >> 4)) << 2;
    x = x >> b4;
    // 高2位是否存在1，有就右移x
    b2 = (!!(x >> 2)) << 1;
    x = x >> b2;
	// 倒数第二位是否是1，有就右移x
    b1 = !!(x >> 1);
	x = x >> b1;
	// 最后一位是否是1
    b0 = x;

    return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

Float

允许使用 if 和 while 后基本上就是模拟过程了

floatScale2

求一个浮点数的 $2$ 倍

unsigned floatScale2(unsigned uf) {
	unsigned sign, exp;

    exp = (uf & 0x7f800000) >> 23;  // 求 exp
    if (exp == 0xFF) return uf;	// 处理NaN和无穷大

    sign = uf & 0x80000000; // 求符号位

    // 非规格化数，直接左移扩大两倍
    if (exp == 0) return uf << 1 | sign;
    // 规格化数增加阶码
    if (++exp == 0xFF) return sign | 0x7f800000;    // 溢出

    return exp << 23 | (uf & 0x807fffff);
}

floatFloat2Int

$float$ 转换对应整数值

int floatFloat2Int(unsigned uf) {
	int e, frac, sign;

    unsigned exp = (uf & 0x7f800000) >> 23;
    e = exp - 127;
    frac = (uf & 0x7fffff) | 0x800000;
    sign = uf >> 31;

    if(e < 0) return 0;   // 如果是 0 和 小于 1 的小数
	if(e > 31) return 0x80000000;	// NaN 或者 无穷大

    // 移动小数点
    if(e > 23) frac <<= (e - 23);
	else frac >>= (23 - e);

    if(!(sign ^ (frac >> 31))) return frac;		// 符号位不变
    if(frac >> 31) return 0x80000000;		// 符号位变化，且当前符号为负，说明溢出
    return ~frac + 1;   // 符号变化未溢出，说明原浮点数为负，返回补码
}

floatPower2

求 $(2.0)^{x}$ 单精度浮点数的位级表示

unsigned floatPower2(int x) {
    int exp = 127 + x;
    if(exp >= 255) return 0x7f800000u;	// 如果发生溢出
    if(exp < 0) return 0;  // 如果数字太小无法用非规格化表示
    return exp << 23;
}

(´-ω-｀)