# CS:APP - Data Lab

Introduction to Computer Systems I (H) @ Fudan University, fall 2019.

## 实验报告

### 1 bitAnd

x & y using only ~ and |.

#### 1.2 解答

 1 2 3 4  int bitAnd(int x, int y) { /* De Morgan's laws */ return ~((~x) | (~y)); } 

### 2 getByte

Extract byte $n$ from word $x$.
Bytes numbered from $0$ (LSB) to $3$ (MSB).

#### 2.1 思路

$1\ \mathrm{byte} = 8\ \mathrm{bit}$，因此将 $x$ 右移 $8n$ 位后，$x$ 最低的字节就是我们需要提取的 byte $n$。之后利用掩码 $\mathtt{0xFF}$ 提取即可。

#### 2.2 解答

 1 2 3 4  int getByte(int x, int n) { /* x AND 0xff returns the lowest byte of x. */ return (x >> (n << 3)) & 0xff; } 

### 3 logicalShift

Shift $x$ to the right by $n$, using a logical shift.
Can assume that $0\le n\le 31$.

#### 3.2 解答

 1 2 3 4 5 6 7 8  int logicalShift(int x, int n) { /* * Mask the highest n bits after doing right shifts, * especially for negative numbers. */ int mask = ~(((0x1 << 31) >> n) << 1); return (x >> n) & mask; } 

### 4 bitCount

Returns count of number of $1$’s in word.

#### 4.1 思路

 1 2 3 4 5   1 0 1 1 0 0 0 1 => 1+0 1+1 0+0 0+1 => 01 +10 00 +01 => 0011 +0001 => 00000100 (= 4) 

#### 4.2 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int bitCount(int x) { /* Add adjacent bits together each time. */ int mask16 = 0x55 | (0x55 << 8); int mask8 = 0x33 | (0x33 << 8); int mask4 = 0x0f | (0x0f << 8); int mask2 = 0xff | (0xff << 16); int mask1 = 0xff | (0xff << 8); mask16 = mask16 | (mask16 << 16); mask8 = mask8 | (mask8 << 16); mask4 = mask4 | (mask4 << 16); x = (x & mask16) + ((x >> 1) & mask16); x = (x & mask8) + ((x >> 2) & mask8); x = (x & mask4) + ((x >> 4) & mask4); x = (x & mask2) + ((x >> 8) & mask2); x = (x & mask1) + ((x >> 16) & mask1); return x; } 

### 5 bang

Compute !x without using !.

#### 5.2 解答

 1 2 3 4 5 6 7 8 9  int bang(int x) { /* Compress the original number to 1 bit. */ x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); return (~x) & 0x1; } 

### 6 tmin

Return minimum two’s complement integer.

#### 6.2 解答

 1 2 3 4  int tmin(void) { /* tmin = 0x80000000 */ return 0x1 << 31; } 

### 7 fitsBits

Return $1$ if $x$ can be represented as an $n$-bit, two’s complement integer. $(1\le n\le 32)$

#### 7.2 解答

  1 2 3 4 5 6 7 8 9 10  int fitsBits(int x, int n) { /* * Convert x to a non-negative number in advance for convenience. If a * non-negative number can be represented as an n-bit, two's complement * integer, it should become 0 after doing right shift by (n - 1) times. */ int sign = x >> 31; x = (x & ~sign) + (~x & sign); // x = x < 0 ? ~x : x; return !(x >> (n + ~0)); } 

### 8 divpwr2

Compute $x / 2^n$, for $0\le n\le 30$.
Round toward zero.

#### 8.2 解答

 1 2 3 4 5 6 7 8 9  int divpwr2(int x, int n) { /* * Positive numbers: x >> n * Negative numbers: (x + (1 << n) - 1) >> n (to round toward 0) */ int sign = x >> 31; int offset = sign & ((0x1 << n) + ~0); return (x + offset) >> n; } 

### 9 negate

Return $-x$.

#### 9.2 解答

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

### 10 isPositive

Return $1$ if $x > 0$, return $0$ otherwise.

#### 10.1 思路

!(x >> 31)101
!x001

#### 10.2 解答

 1 2 3 4 5 6 7 8  int isPositive(int x) { /* * Positive numbers: !(x >> 31) = 1, !x = 0, expected 1 * Negative numbers: !(x >> 31) = 0, !x = 0, expected 0 * Zero: !(x >> 31) = 1, !x = 1, expected 0 */ return (!(x >> 31)) ^ (!x); } 

### 11 isLessOrEqual

If $x\le y$ then return $1$, else return $0$.

#### 11.2 解答

 1 2 3 4 5 6 7 8 9  int isLessOrEqual(int x, int y) { /* * If x and y have the same sign, judge the sign of (y - x); * otherwise, the negative one is smaller than the positive one. */ int sign_diff = x ^ y; int diff = y + ~x + 1; return (((sign_diff & x) | (~sign_diff & ~diff)) >> 31) & 0x1; } 

### 12 ilog2

Return $\lfloor \log_2{x}\rfloor$, where $x>0$.

#### 12.2 解答

 1 2 3 4 5 6 7 8 9  int ilog2(int x) { /* Find the highest 1 in x through binary search. */ int result = (!!(x >> 16)) << 4; result += (!!(x >> (result + 8))) << 3; result += (!!(x >> (result + 4))) << 2; result += (!!(x >> (result + 2))) << 1; result += (!!(x >> (result + 1))); return result; } 

### 13 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 $\mathrm{NaN}$, return argument.

#### 13.2 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13  unsigned float_neg(unsigned uf) { /* * If uf is NaN, return uf; * otherwise, convert the sign bit to the opposite. */ unsigned sign_mask = 0x1 << 31; unsigned exp_mask = 0xff << 23; unsigned frac_mask = 0x7fffff; unsigned exp = uf & exp_mask; unsigned frac = uf & frac_mask; if (exp == exp_mask && frac) return uf; // uf is NaN return uf ^ sign_mask; } 

### 14 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.

#### 14.1 思路

• 如果被舍去部分大于 $\mathtt{0x80}$，则需要进位；
• 如果被舍去部分等于 $\mathtt{0x80}$，且被保留部分最低位为 $1$，则需要进位；
• 其余情况不进位。

#### 14.2 解答

  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  unsigned float_i2f(int x) { unsigned int_min = 0x80000000; unsigned exp = 31; unsigned carry = 0; unsigned new_x = 0; /* Deal with special cases. */ if (x == 0) return 0; if (x == int_min) return 0xcf000000; /* Convert x to positive for convenience. */ if (x < 0) { x = -x; /* Set the sign bit. */ new_x |= int_min; } /* Move the fraction bits to the top. */ while (!(x & int_min)) { x <<= 1; --exp; } /* Set the exponent bits. */ new_x |= (exp + 127) << 23; /* Judge whether carry is 0 or 1. */ if ((x & 0x1ff) == 0x180 || (x & 0xff) > 0x80) carry = 1; // else carry = 0; /* Set the fraction bits. */ new_x |= (x >> 8) & 0x7fffff; new_x += carry; return new_x; } 

### 15 float_twice

Return bit-level equivalent of expression $2f$ 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 $\mathrm{NaN}$, return argument.

#### 15.1 思路

• 当 $f$ 是 $\pm 0$ 时，直接返回；
• 当 $f$ 是 $\mathrm{NaN}$ 时，直接返回；
• 当 $f$ 是 subnormal number 时，直接将 fraction bits 左移 $1$ 位后返回3
• 其余情况，将 exponent bits 加 $1$。

#### 15.2 解答

  1 2 3 4 5 6 7 8 9 10 11  unsigned float_twice(unsigned uf) { /* Deal with special cases. */ unsigned sign_mask = 0x1 << 31; unsigned exp_mask = 0xff << 23; unsigned sign = uf & sign_mask; unsigned exp = uf & exp_mask; if (uf == 0 || uf == sign_mask) return uf; // uf is +0 / -0 if (exp == exp_mask) return uf; // uf is NaN if (exp == 0) return (uf << 1) | sign; // uf is a subnormal number return uf + (0x1 << 23); } 

## 运行结果

### dlc

 1 2  ./dlc bits.c ./dlc bits.c -e 

### btest

 1  ./btest 

## 测试环境

• Ubuntu 18.04.3 LTS (GNU/Linux 5.0.0-29-generic x86_64)
• GCC 7.4.0
• GNU Make 4.1

## 参考资料

1. 参考了 @codinfox 的思路。 ↩︎ ↩︎

2. 无需担心溢出到 exponent bits 的问题，这是 IEEE 标准所保证的。 ↩︎