盒子
盒子
文章目录
  1. 实验内容
    1. bitAnd
    2. getByte
    3. logicalShift
    4. bitCount
    5. bang
    6. tmin
    7. fitsBits
    8. divpwr2
    9. negate
    10. isPositive
    11. isLessOrEqual
    12. ilog2
    13. float_neg
    14. float_i2f
    15. float_twice

CMU15213:CSAPP 实验一:DataLab

实验内容

《深入理解计算机系统》的第一个实验,内容包括位操作,用二进制表示整数,浮点数,以及相应的操作。实验限定了可选用的操作符,并且有最大次数限制,总体来讲还是非常有趣的。

bitAnd

只使用 ~ 和 | 实现 &

De Morgan定律

1
2
3
4
5
6
7
8
9
10
/*
* 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

从一个整数(4字节)中提取第0,1,2,3个字节。每个字节8bits,所以通过右移8*n位,然后取最后8位bits

1
2
3
4
5
6
7
8
9
10
11
/*
* 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 x>>(n<<3) & 0xFF;
}

logicalShift

将一个数逻辑右移,当x为负数时,代码实际上进行的是算术右移,所以要将右移的1改为0

最高位右移之后的位置为:32-n,所以将-1[1..1]左移动31-n位,得到[1..10..0]。取反之后再&算术右移的数即可。

但由于不能使用-,使用-n=~n+1. 32-n= 32+~n+1。并且使得每次移位的范围在[0,31]之间,分成两次移位。

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* 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) {
int tmp = (~0)<<(32 + (~n));
tmp = tmp << 1;
return x>>n & (~tmp);
}

bitCount

计算二进制中bit为1的个数,由于不能使用循环等操作,这道题难度很大。可以采用一种分治的思想解决。

为了能够将对应位上的数字相加,需要产生5个mask,分别是0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0x0000ffff。 分别代表了[1,2,4,8,16]个0和1间隔。

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
/*
* 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 _mask1 = 0x55 | (0x55 << 8); // 0x5555
int _mask2 = 0x33 | (0x33 << 8); // 0x3333
int _mask3 = 0x0f | (0x0f << 8); // 0x0f0f
int mask1 = _mask1 | (_mask1 << 16); // 0x55555555 = [0101...0101]
int mask2 = _mask2 | (_mask2 << 16); // 0x33333333 = [0011...0011]
int mask3 = _mask3 | (_mask3 << 16); // 0x0f0f0f0f = [00001111...00001111]
int mask4 = 0xff | (0xff << 16); // 0x00ff00ff = [00000000111111110000000011111111]
int mask5 = 0xff | (0xff << 8); // 0x0000ffff = [00000000000000001111111111111111]
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

计算!x,但不能使用!

只用当x为0时,!x=1, 观察得到只有0和-0的最高位都不为1,其它的都至少有一个1(tmin有两个,-tmin=tmin)。

1
2
3
4
5
6
7
8
9
10
/*
* 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;
}

tmin

计算tmin,直接1<<31即可

1
2
3
4
5
6
7
8
9
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1<<31;
}

fitsBits

这题关键点是理解题意。如果x能够被表示成n-bit的补码,则返回1. 其实问的是,用一个长度为n-bit的二进制表示补码,对应范围为[n-tmin, n-tmax],问x是否在该范围内。

观察n-bit能够表示的范围,如果将这个数右移n-1位,如果x为正,此时x全为0,如果x为负,那么x全为1(为-1)。再将x+1之后再右移1位,此时x应该全为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* 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) {
x = (x>>(n + ~0)) + 1;
return !(x>>1);
}

divpwr2

计算x/(2^n), 并且向零取整

  • 当x为整数的时候,直接右移n为即可。
  • 当x为负数的时候,由于要向上取整,所以需要加上偏移量。ans = (x+(1<>k

所以这道题的关键是先判断是否为负数,若是,加上对应的偏移量。

1
2
3
4
5
6
7
8
9
10
11
12
/*
* 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 s = (x >> 31) & 1;
return (x + (s<<n) + ~s + 1) >> n;
}

negate

计算-x。-x=~x+1

1
2
3
4
5
6
7
8
9
10
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}

isPositive

如果x>0, 返回1。否则返回0

这道题咋一看很简单,只需要判断最高位。但是0并不是一个正数,所以需要特殊处理。

  • x为0,!x=1, ~x的最高位为1,相减得0
  • x为整数,!x=0, ~x的最高位为1,相减得1
  • x为负数,!x=0, ~x的最高位为0,相减得0
1
2
3
4
5
6
7
8
9
10
11
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
int z = !x;
return (((~x)>>31) & 1) + (~z + 1);
}

isLessOrEqual

判断 x<=y
如果直接用y-x,会溢出。所以这题需要先判断x和y的两者符号是否相同。不同的情况很好处理,如果相同,两者相减并不会发生溢出,再判断即可。

如果两者相同,x-y<=0, x-y-1<=-1, 即x+~y+1-1<=-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 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 sx = (x>>31) & 1;
int sy = (y>>31) & 1;
int sign_diff = sx & !sy;
int sign_same = !(sx^sy) & (((x+~y)>>31) & 1);
return sign_diff | sign_same;
}

ilog2

ilog2(16)=4

本质上就是求x的最高位1的位置,可以使用上面bitCount中分治法的思想。ilog2(x)的最大值为31,可以表示为 ilog2(x) = 16a+8b+4c+2d+1e。其中a,b,c,d,e为0或1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* 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) {
// max(x) = 31
// x can be replace by : x = 16*a+8*b+4*c+2*d+1*e
int ans = 0;
ans += (!!(x>>16)) << 4;
ans += (!!(x>>(8+ans))) << 3;
ans += (!!(x>>(4+ans))) << 2;
ans += (!!(x>>(2+ans))) << 1;
ans += (!!(x>>(1+ans))) << 0;
return ans;
}

float_neg

用unsigned x表示float,并返回-x

先判断uf是否为NaN,如果是,返回NaN,如果不是的话,返回-uf即可。当浮点数中阶数全为1,而尾数不为0时,表示该数为NaN。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* 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 t = uf & 0x7fffffff;
if (t > 0x7f800000) return uf;
return uf ^ 0x80000000;
}

float_i2f

将一个int数转化为float

x=(s<<31) | (exponent<<23) | fraction

先得到符号位,然后如果x=0,或者x=-tmin,直接返回相应的float。如果x为负数,转化为整数考虑。再分别计算该数的exponent和fraction,在计算fraction的时候需要注意向偶数进位,并且进位之后exponent是否需要改变。具体的细节见代码注释

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
26
27
28
29
30
31
32
33
34
35
36
37
/*
* 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) {
// return (s<<31)|(exponent<<23)|fraction
int s = (x>>31) & 1; //sign
int exponent;
int fraction = 0;
int fraction_mask;
int delta;
int i = 30;
if (x == 0) return x; //x=0
else if (x == 0x80000000) { //x=-tmin, exponent = 31 + 127
exponent = 158;
} else {
if (s) x = -x; //if x is negative, change to positive
while(!(x>>i)) i--; //right shift until x=0
exponent = i + 127;
x = x << (31 - i); //clean zeros in higher bits
fraction_mask = 0x7fffff;
fraction = fraction_mask & (x >> 8); //get fraction
x = x & 0xff; //the lower 8 bits will be truncated
delta = (x > 128) || ((x == 128) && (fraction & 1)); //if x>=odd.5, delta = 1
fraction += delta;
if (fraction >> 23) { //if fraction is larger than 23 bits
exponent += 1;
fraction &= fraction_mask;
}
}
return (s<<31) | (exponent<<23) | fraction;
}

float_twice

将给定的unsigned uf表示的float * 2

如果uf是denormalized,uf的二进制左移1就是该数乘2。如果uf 2还是denormalized,好理解。如果uf 2变成了normalized,阶码变为1,尾数变为0.也成立。

如果uf是normalized,直接将uf的阶码+1,但如果uf的阶码+1之后全为1,就变成了inf,需要将尾数全部置为0.

如果uf是NaN或者inf,直接返回uf。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* 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) {
if ((uf & 0x7f800000) == 0) { //denormalized
return (uf & 0x80000000) | (uf << 1);
} else if ((uf & 0x7f800000) != 0x7f800000) { //normalized
uf += (1 << 23);
if ((uf & 0x7f800000) == 0x7f800000) uf = uf >> 23 << 23;
return uf;
} else return uf; // NaN or inf
}

整个实验内容让我更深入的理解计算机如何用二进制表示整数和浮点数,收获很大。可以配套CMU的网上课程学习该书,效果会更好。