深入理解计算机系统(第二版) 家庭作业第二章

正在看《深入理解计算机系统》这本书，课后茫茫多的习题，看着就让人发怵。。

做的时候也需要验证一下对错，所以在网上找了很多相关的题解。顺便就在这里记一下了。

先放一下源码地址：

第二章各种编码和绕来套取的计算当时差点把我劝退，做个小结就是一般来说整数用补码编码，浮点数用 IEEE 浮点编码，和小心精度问题。

2.55

先上 show-bytes.c 源码：

/* $begin show-bytes */
#include <stdio.h>
/* $end show-bytes */
#include <stdlib.h>
#include <string.h>
/* $begin show-bytes */

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len) {
    int i;
    for (i = 0; i < len; i++)
	printf(" %.2x", start[i]);    //line:data:show_bytes_printf
    printf("\n");
}

void show_int(int x) {
    show_bytes((byte_pointer) &x, sizeof(int)); //line:data:show_bytes_amp1
}

void show_float(float x) {
    show_bytes((byte_pointer) &x, sizeof(float)); //line:data:show_bytes_amp2
}

void show_pointer(void *x) {
    show_bytes((byte_pointer) &x, sizeof(void *)); //line:data:show_bytes_amp3
}
/* $end show-bytes */


/* $begin test-show-bytes */
void test_show_bytes(int val) {
    int ival = val;
    float fval = (float) ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}
/* $end test-show-bytes */

void simple_show_a() {
/* $begin simple-show-a */
int val = 0x87654321;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
/* $end simple-show-a */
}

void simple_show_b() {
/* $begin simple-show-b */
int val = 0x12345678;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
/* $end simple-show-b */
}

void float_eg() {
  int x = 3490593;
  float f = (float) x;
  printf("For x = %d\n", x);
  show_int(x);
  show_float(f);

  x = 3510593;
  f = (float) x;
  printf("For x = %d\n", x);
  show_int(x);
  show_float(f);

}

void string_ueg() {
/* $begin show-ustring */
const char *s = "ABCDEF";
show_bytes((byte_pointer) s, strlen(s)); 
/* $end show-ustring */
}

void string_leg() {
/* $begin show-lstring */
const char *s = "abcdef";
show_bytes((byte_pointer) s, strlen(s)); 
/* $end show-lstring */
}

void show_twocomp() 
{
/* $begin show-twocomp */
    short x = 12345; 
    short mx = -x; 
  
    show_bytes((byte_pointer) &x, sizeof(short)); 
    show_bytes((byte_pointer) &mx, sizeof(short)); 
/* $end show-twocomp */
}

int main(int argc, char *argv[])
{
    int val = 12345;

    if (argc > 1) {
        if (argc > 1) {
            val = strtol(argv[1], NULL, 0);
        }
        printf("calling test_show_bytes\n");
        test_show_bytes(val);
    } else {
        printf("calling show_twocomp\n");
        show_twocomp();
        printf("Calling simple_show_a\n");
        simple_show_a();
        printf("Calling simple_show_b\n");
        simple_show_b();
        printf("Calling float_eg\n");
        float_eg();
        printf("Calling string_ueg\n");
        string_ueg();
        printf("Calling string_leg\n");
        string_leg();
    }
    return 0;
}

用 GCC 编译：

// mac os 11.1
gcc -m64 show-bytes.c -o show-bytes

run 一下：

./show-bytes

输出：

calling show_twocomp
 39 30
 c7 cf
Calling simple_show_a
 21
 21 43
 21 43 65
Calling simple_show_b
 78
 78 56
 78 56 34
Calling float_eg
For x = 3490593
 21 43 35 00
 84 0c 55 4a
For x = 3510593
 41 91 35 00
 04 45 56 4a
Calling string_ueg
 41 42 43 44 45 46
Calling string_leg
 61 62 63 64 65 66

2.56

可以在后面加参数，就可以试不同的示例值了：

// 输入
./show-bytes 1

// 输出 顺便看出来是小端模式。
calling test_show_bytes
 01 00 00 00
 00 00 80 3f
 58 f9 14 e4 fe 7f 00 00

// 输入
./show-bytes 996

// 输出
calling test_show_bytes
 e4 03 00 00
 00 00 79 44
 58 79 ad ec fe 7f 00 00

2.57

增加三个函数并修改测试函数：

void show_short(short x) {
  show_bytes((byte_pointer) &x, sizeof(short));
}

void show_long(long x) {
  show_bytes((byte_pointer) &x, sizeof(long));
}

void show_double(double x) {
  show_bytes((byte_pointer) &x, sizeof(double));
}

void test_show_bytes(int val) {
    int ival = val;
    float fval = (float) ival;
    int *pval = &ival;
  
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
  
    short sval = (short) ival;
    long lval = (long) ival;
    double dval = (double) ival;

    show_short(sval);
    show_long(lval);
    show_double(dval);
}

重新编译，测试结果如下，注意最后三行输出是新加的：

// 输入
./show-bytes 1

// 输出
calling test_show_bytes
 01 00 00 00
 00 00 80 3f
 58 39 b0 e5 fe 7f 00 00
 01 00
 01 00 00 00 00 00 00 00
 00 00 00 00 00 00 f0 3f

// 输入
./show-bytes 996

// 输出
calling test_show_bytes
 e4 03 00 00
 00 00 79 44
 58 a9 35 ed fe 7f 00 00
 e4 03
 e4 03 00 00 00 00 00 00
 00 00 00 00 00 20 8f 40

2.58

/*
 * is-little-endian.c
 */

#include <stdio.h>
#include <assert.h>

typedef unsigned char* byte_pointer;

int is_little_endian() {
  int test_num = 0xff;
  byte_pointer byte_start = (byte_pointer) &test_num;

  if (byte_start[0] == 0xff) {
    return 1;
  }
  return 0;
}

int is_little_endian_other(){
    int a = 1;
    return *((char*)&a);
}

int main(int argc, char* argv[]) {
  assert(is_little_endian());
  return 0;
}

2.59

(x & 0xFF) | (y & ~0xFF)

2.60


/*
 * replace-byte.c
 */

#include <stdio.h>
#include <assert.h>

unsigned replace_byte(unsigned x, int i, unsigned char b) {
  if (i < 0) {
    printf("error: i is negetive\n");
    return x;
  }
  if (i > sizeof(unsigned)-1) {
    printf("error: too big i");
    return x;
  }

  // 1 byte 有 8 bits， << 3 就是 * 8
  unsigned mask = ((unsigned) 0xFF) << (i << 3);
  unsigned pos_byte = ((unsigned) b) << (i << 3);

  return (x & ~mask) | pos_byte;
}

int main(int argc, char *argv[]) {
  unsigned rep_0 = replace_byte(0x12345678, 0, 0xAB);
  unsigned rep_3 = replace_byte(0x12345678, 3, 0xAB);

  assert(rep_0 == 0x123456AB);
  assert(rep_3 == 0xAB345678);
  return 0;
}

2.61


// A x 的任何位都等于 1
!~x

// B x 的任何位都等于 0
!x

// C x 的最高有效字节中的位都等于 1
!~(x >> ((sizeof(int) - 1) << 3))

// D x 的最低有效字节中的位都等于 0
!(x & 0xFF)

2.62

/*
 * int-shifts-are-arithemetic.c
 */

#include <stdio.h>
#include <assert.h>

int int_shifts_are_arithemetic() {
  int num = -1;
  return !(num ^ (num >> 1));
}

int main(int argc, char* argv[]) {
  assert(int_shifts_are_arithemetic());
  return 0;
}

2.63

/*
 * srl-sra.c
 */

#include <stdio.h>
#include <assert.h>

// 将 xrsl 的第 w-k-1 位扩展到前 k 个高位
int sra(int x, int k) {
  int xsrl = (unsigned) x >> k;

  int w = sizeof(int) << 3;
  // mask 的前 k 高位全是 1
  int mask = (int) -1 << (w - k);
  // m 最高位是 1，其他都是 0
  int m = 1 << (w - 1);
  // x & m，确定符号位是 1 还是 0。
  // 然后如果符号位是 1，!(x & m) 为 0，0 - 1 等于 -1，mask &= -1 还是他本身。
  // 如果符号位是 0，!(x & m) 为 1，1 - 1 等于 0，mask &= 0 为 0。
  mask &= !(x & m) - 1;
  return xsrl | mask;
}

// 前 k 高位清零即可
unsigned srl(unsigned x, int k) {
  unsigned xsra = (int) x >> k;

  int w = sizeof(int) << 3;
  int mask = (int) -1 << (w - k);
  return xsra & ~mask;
}

int main(int argc, char* argv[]) {
  unsigned test_unsigned = 0x12345678;
  int test_int = 0x12345678;

  assert(srl(test_unsigned, 4) == test_unsigned >> 4);
  assert(sra(test_int, 4) == test_int >> 4);

  test_unsigned = 0x87654321;
    test_int = 0x87654321;

    assert (srl (test_unsigned, 4) == test_unsigned >> 4);
    assert (sra (test_int, 4) == test_int >> 4);

  return 0;
}

2.64

int any_even_one(unsigned x) {
    return !!(0x55555555 & x);
}

2.65

// x 的每个位进行异或，如果为 0 就说明是偶数个 1，如果为 1 就是奇数个 1 。
// 通过算数右移一半的位数，相当于把左半部分位数降低到和右半部分一致，只关心右半部分异或结果就好。
int even_ones(unsigned x){
    x ^= (x >> 16);
    x ^= (x >> 8);
    x ^= (x >> 4);
    x ^= (x >> 2);
    x ^= (x >> 1);
    return !(x & 1);
}

2.66

实现掩膜，数位中只剩下最左边的 1，其他位都是 0。如果 x 为 0,那么函数返回 0。

利用移位操作，首先将 x 右移再或，分别利用 1,2,4,8,16，得到从最左边的 1 后面全部为 1，然后再右移1位，取异或。

int leftmost_one(unsigned x) {
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x^(x>>1);
}

2.67

A：

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior it undefined.

32位机器上没有定义移位32次，所以需要分多次左移。

/*
 * int-size-is-32.c
 */

#include <stdio.h>
#include <assert.h>

/* The following function does not run properly on some machine */
/*
int bad_int_size_is_32() {
  int set_msb = 1 << 31;
  int beyond_msb = 1 << 32;

  return set_msb && !beyond_msb;
}
*/

int int_size_is_32() {
  int set_msb = 1 << 31;
  int beyond_msb = set_msb << 1;

  return set_msb && !beyond_msb;
}

int int_size_is_32_for_16bit() {
  int set_msb = 1 << 15 << 15 << 1;
  int beyond_msb = set_msb << 1;

  return set_msb && !beyond_msb;
}

int main(int argc, char *argv[]) {
  assert(int_size_is_32());
  assert(int_size_is_32_for_16bit());
  return 0;
}

2.68

让 x 的最低 n 位变 1。

/*
 * lower-one-mask.c
 */
#include <stdio.h>
#include <assert.h>

/*
 * Mask with least signficant n bits set to 1
 * Example: n = 6 -> 0x3F, n = 17 -> 0x1FFFF
 * Assume 1 <= n <= w
 */
int lower_one_mask(int n) {
  int w = sizeof(int) << 3;
  return (unsigned) -1 >> (w - n);
}

int main(int argc, char* argv[]) {
  assert(lower_one_mask(6) == 0x3F);
  assert(lower_one_mask(17) == 0x1FFFF);
  assert(lower_one_mask(32) == 0xFFFFFFFF);
  return 0;
}