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
判断一个数是不是
注意到 并且它们每一位恰好是反的，将其中一个按位取反再异或，将这个结果取否定即可，但是需要排除一下 ，使用 !!(x+1)，这个表达式只会排除
1
2
3
| int isTmax(int x) {
return !(~(x + 1) ^ x) & !!(x + 1);
}
|
allOddBits
判断一个二进制数奇数位是不是都是1
构造一个掩码 mask=0xAAAAAAAA ，和 按位与提取出 的奇数位，提取出后只有和 一样才能返回 ，所以进行异或运算后取否定即可得到结果
这也提供了一种判断 和 是否相等的方法 !(a ^ b)
1
2
3
4
5
6
| int allOddBits(int x) {
int mask = 0xAA;
mask = (mask << 8) | mask;
mask = (mask << 16) | mask;
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
实现三目运算符
为准确提取 或 首先需要实现 非零时返回 ，为零时返回
注意到之前可以判断是否相等，首先想到判断和 是否相等 !(x ^ 0)
这时很好的区分了零和非零，为零返回 ，非零返回
不能使用减号，不如考虑取反加 ，为零返回 ，非零返回 恰好再取一次反得到结果
此时 为真提取 ，否则提取 即可
1
2
3
4
| int conditional(int x, int y, int z) {
int key = ~(~(!(x ^ 0)) + 1);
return (y & key) | (z & ~key);
}
|
isLessOrEqual
判断是否小于等于
简单来说直接求 再判断符号位是什么即可
但是异号一定会溢出，所以只能同号这样求，异号时 负 正一定成立
1
2
3
4
5
6
7
8
| int isLessOrEqual(int x, int y) {
int xOp, yOp;
xOp = x >> 31;
yOp = y >> 31;
return (xOp & !yOp) |
(~(xOp ^ yOp) &
!((y + (~x + 1)) >> 31));
}
|
logicalNeg
实现逻辑否
也就是为零时逻辑否是 ，非零时逻辑否是
注意到 ，其他数取相反数符号位几乎都会改变
但是 但注意到它和 的最高位不同
采用 x|(~x+1) 得到只有 最高位是 ，做算术右移再加 即可
1
2
3
| int logicalNeg(int x) {
return ((x | (~x + 1)) >> 31) + 1;
}
|
howManyBits
求将 表示为二进制补码所需要的最小位
不难发现排开符号位只需要找到第一个 所在的位置序号（最低有效位）加上 （表示符号）即可，不妨只考虑正数或者说把所有数转化为正数再考虑
sign = x >> 31
x = (sign & ~x) | (~sign & x);
做个映射，前 位如果有 ，位数二进制表示一定是
往后 位如果有 ，位数二进制表示一定是
往后 位如果有 ，位数二进制表示一定是
往后 位如果有 ，位数二进制表示一定是
倒数第二位如果是 ， 位数二进制表示一定是
最后一位如果是 ， 位数二进制表示一定是
类似二分查找，统一化为
1
2
3
|
b_k = (!!(x >> k)) << f(k)-1;
x = x >> b_k;
|
最终代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int howManyBits(int x) {
int b16, b8, b4, b2, b1, b0;
int sign = x >> 31;
x = (sign & ~x) | (~sign & x);
b16 = (!!(x >> 16)) << 4;
x = x >> b16;
b8 = (!!(x >> 8)) << 3;
x = x >> b8;
b4 = (!!(x >> 4)) << 2;
x = x >> b4;
b2 = (!!(x >> 2)) << 1;
x = x >> b2;
b1 = !!(x >> 1);
x = x >> b1;
b0 = x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}
|
Float
允许使用 if 和 while 后基本上就是模拟过程了
floatScale2
求一个浮点数的 倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| unsigned floatScale2(unsigned uf) {
unsigned sign, exp;
exp = (uf & 0x7f800000) >> 23;
if (exp == 0xFF) return uf;
sign = uf & 0x80000000;
if (exp == 0) return uf << 1 | sign;
if (++exp == 0xFF) return sign | 0x7f800000;
return exp << 23 | (uf & 0x807fffff);
}
|
floatFloat2Int
转换对应整数值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
if(e > 31) return 0x80000000;
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
求 单精度浮点数的位级表示
1
2
3
4
5
6
| unsigned floatPower2(int x) {
int exp = 127 + x;
if(exp >= 255) return 0x7f800000u;
if(exp < 0) return 0;
return exp << 23;
}
|
