【CSAPP】家庭作业2.55~2.76

2.55*

问：在你能访问的不同的机器上，编译show_bytes.c并运行代码，确定这些机器的字节顺序。
答：

// show_bytes.c
#include <stdio.h>typedef unsigned char *byte_pointer;void show_bytes(byte_pointer start, size_t len)
{for (size_t i = 0; i < len; ++i) {printf("%.2X ", start[i]);}printf("\n");
}void show_int(int x)
{show_bytes((byte_pointer)&x, sizeof(int));
}

在x86_64上，运行结果为：

// show_int(0x87654321);
[liheng@localhost2 2]$ ./a.out 
21 43 65 87 

低位字节保存在低地址，该机器按小端顺序存储多字节对象。

2.56*

问：试着用不同的示例值来运行show_bytes.c。
答：

// show_int(0x11223344);
[liheng@localhost2 2]$ ./a.out 
44 33 22 11 

// show_int(0x22);
[liheng@localhost2 2]$ ./a.out 
22 00 00 00 

// show_int(0x11000000);
[liheng@localhost2 2]$ ./a.out 
00 00 00 11 

2.57*

问：编写并运行程序show_short、show_long和show_double。
答：

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));
}

在x86_64上，运行结果为：

// show_short(0x1234);
// show_long(0x1234);
// show_double(0x1234);
[liheng@localhost2 2]$ ./a.out 
34 12 
34 12 00 00 00 00 00 00 
00 00 00 00 00 34 B2 40 

// show_short(0x1030);
// show_long(0x1030);
// show_double(0x1030);
[liheng@localhost2 2]$ ./a.out 
30 10 
30 10 00 00 00 00 00 00 
00 00 00 00 00 30 B0 40 

2.58**

问：编写过程is_little_endian，当在小端法机器上运行时返回1，否则返回0。
答：

int is_little_endian()
{uint32_t x = 0x12345678; // #include <stdint.h>return *(uint8_t *)&x == (uint8_t)0x78;
}

在x86_64上，运行结果为：

// printf("is_little_endian: %d\n", is_little_endian());
[liheng@localhost2 2]$ ./a.out 
is_little_endian: 1

2.59**

问：编写一个C表达式，它生成一个字，由x的最低有效字节和y中剩下的字节组成。对于x = 0x89ABCDEF、y = 0x76543210得到0x765432EF。
答：表达式为(x & 0xFF) | (y & ~0xFF)。

2.60**

问：假设我们将一个w位的字中的字节从0（最低位字节）到w / 8 - 1（最高位字节）编号，写出下面C函数的代码，它会返回一个无符号值，其中参数x的字节i被替换成字节b。

unsigned replace_byte(unsigned x, int i, unsigned char b);
// replace_byte(0x12345678, 2, 0xAB) --> 0x12AB5678
// replace_byte(0x12345678, 0, 0xAB) --> 0x123456AB

答：
replace_byte的实现：

unsigned replace_byte(unsigned x, int i, unsigned char b)
{unsigned bits = i << 3;unsigned x1 = x & ~(0xFF << bits);unsigned b1 = b << bits;return x1 | b1;
}

在x86_64上的运行结果：

// printf("%p\n", replace_byte(0x12345678, 4, 0xAB));
// printf("%p\n", replace_byte(0x12345678, 3, 0xAB));
// printf("%p\n", replace_byte(0x12345678, 2, 0xAB));
// printf("%p\n", replace_byte(0x12345678, 1, 0xAB));
// printf("%p\n", replace_byte(0x12345678, 0, 0xAB));
[liheng@localhost2 2]$ ./a.out 
0x123456ab
0xab345678
0x12ab5678
0x1234ab78
0x123456ab

位级整数编码规则

在接下来的作业中，我们特意限制了你能使用的编程结构，来帮助你更好地理解C语言的位级、逻辑和算术运算。你的代码必须遵守以下规则：

• 假设

1. 整数用补码形式表示。
2. 有符号数的右移是算术右移。
3. 数据类型int是w（一定是8的整数倍）位长的。某些题目会给出w的值。

• 禁止使用

4. 条件语句if或? : 、循环、分支语句、函数调用和宏调用。
5. 除法、模运算和乘法。
6. 相对比较运算<、>、<=和>=。

• 允许的运算

7. 所有的位级和逻辑运算。
8. 左移和右移，位移量只能在0 ~ w-1之间。
9. 加法和减法。
10. 相等==和不相等!=。
11. 整型常数INT_MIN和INT_MAX。
12. 对int和unsigned进行隐式或显式强制类型转换。

个别题目有特殊的限制。

2.61**

问：写一个C表达式，在下列描述的条件下产生1，在其他情况下得到0，假设x是int类型。
答：

1. x的任何位都等于1。

!~x

2. x的任何位都等于0。

!x;

3. x的最低有效字节中的位都等于1。

!~(x | ~0xFF)

4. x的最高有效字节中的位都等于0。

!((0xFF << ((sizeof(int) - 1) << 3)) & x);

2.62***

问：编写一个函数int_shifts_are_arithmetic()，在对int类型的数使用算术右移的机器上运行时这个函数返回1，其他情况下返回0。
答：

int int_shifts_are_arithmetic()
{int x = -1;return (x >> 8) == x;  // return !(x ^ (x >> 8));
}

在x86_64上的运行结果：

// printf("%d\n", int_shifts_are_arithmetic());
[liheng@localhost2 2]$ ./a.out 
1

2.63***

问：将下面的C函数代码补充完整。函数srl用算术右移（由值xsra给出）完成逻辑右移，后面的操作不包括右移或者除法。函数sra用逻辑右移（由值xsrl给出）来完成算术右移，后面的操作不包括右移或者除法。w = sizeof(int) * 8，k的取值范围是0 ~ w-1。
答：

unsigned srl(unsigned x, in k)
{unsigned xsra = (int)x >> k;  // 算术右移的值int mask = ((1 << k) - 1) << ((sizeof(int) << 3) - k);return xsra & ~mask;
}int sra(int x, int k)
{int xsrl = (unsigned)x >> k;  // 逻辑右移的值int sign = !!(x & (1 << ((sizeof(int) << 3) - 1)));int mask = ((sign << k) - sign) << ((sizeof(int) << 3) - k);return xsrl | mask;
}

在x86_64上的运行结果：

// printf("%p\n", srl(-1, 0));
// printf("%p\n", srl(-1, 16));
// printf("%p\n", srl(-1, 31));
// printf("%p\n", sra(-1, 0));
// printf("%p\n", sra(-1, 16));
// printf("%p\n", sra(-1, 31));
// printf("%p\n", sra(0x0F000000, 16));
[liheng@localhost2 2]$ ./a.out 
0xffffffff
0xffff
0x1
0xffffffff
0xffffffff
0xffffffff
0xf00

2.64*

问：实现一个函数，入参是一个整型x（w = 32），如果有一个奇数位是1，就返回1，否则返回0。

首先需要构造32位的掩码10[10]...，使用该掩码去掉x中的偶数位，再判断奇数位是否存在一个1。
32位的掩码10[10]...的十六进制表示为0x55555555。
答：

int any_odd_one(unsigned x)
{int mask = 0x55555555;return x & mask;
}

在x86_64机器上的运行结果：

// printf("%d\n", any_odd_one(0x1));
// printf("%d\n", any_odd_one(0x2));
[liheng@localhost2 2]$ ./a.out 
1
0

2.65****

问：实现一个函数，入参是一个整型x（w = 32），当x有奇数个值为1的位时，返回1，否则返回0。
答：

int odd_ones(unsigned x)
{x ^= x >> 16;x ^= x >> 8;x ^= x >> 4;x ^= x >> 2;x ^= x >> 1;return x & 0x1;
}

第一个^=运算把x的0~15位和16~31位的^运算结果放在了x的0~15位；第二个^=运算把x（上一步的运算结果）的0~7位和8~15位的^运算结果放在了x的0~7位，以此类推。最终x的第0位上放的就是初值的x的所有位的^结果。

1 ^ 1 = 0、0 ^ 0 = 0、1 ^ 0 = 1，异或会抵消掉相同的位，把值归0，且异或具有结合律。因此只要把x中的所有位按任意顺序异或一遍，最终结果为1的话就说明它包含奇数个值为1的位。

在x86_64机器上的运行结果：

// printf("%d\n", odd_ones(0x0));  // 0个值为1的位
// printf("%d\n", odd_ones(0x1));  // 1个值为1的位
// printf("%d\n", odd_ones(0x3));  // 2个值为1的位
// printf("%d\n", odd_ones(-1));  // 32个值为1的位
// printf("%d\n", odd_ones(369));  // 5个值为1的位
// printf("%d\n", odd_ones(11825));  // 7个值为1的位
[liheng@localhost2 2]$ ./a.out 
0
1
0
0
1
1

2.66***

问：实现一个函数，入参是一个整型x（w = 32），返回一个掩码指示最高位的1的位置。如输入0xFF00返回0x8000，输入0x6600返回0x4000，输入0返回0。
答：

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

从x的值为1的最高位算起往它的低位开始数，第一次|=运算的结果把2个位设置为1，第二次|=运算的结果把4个位设置为1，以此类推，把全32位都设置为1。最后把结果右移1位再加1，就得到了指示最高位的1的位置的数。

在x86_64机器上的运行结果：

// printf("%d\n", leftmost_one(0x0));
// printf("%p\n", leftmost_one(0xF));
// printf("%p\n", leftmost_one(0x6600));
// printf("%p\n", leftmost_one(0x8000));
// printf("%p\n", leftmost_one(0x46531));
// printf("%p\n", leftmost_one(-1));
[liheng@localhost2 2]$ ./a.out 
0
0x8
0x4000
0x8000
0x40000
0x80000000

2.67**

问：实现一个函数，当在一个int是32位的机器上运行时，该程序产生1，其他情况产生0。不允许使用sizeof。
下面是开始的尝试：

int bad_int_size_is_32()
{int set_msb = 1 << 31;int beyond_msb = 1 << 32;// set_msb非零时，int_size >= 32；beyond_msb为零时，int_size <= 32return set_msb && !beyond_msb;  
}

当我们在SUN SPARC这样的32位机器上编译运行时，这个过程返回的却是0。编译器打印了一句warning：

warning: left shift count >= width of type

答：

1. 我们的代码在哪个方面没有遵守C语言标准？
   C标准没有明确规定当移位操作的位数大于等于变量的宽度时的行为。有的机器上1 << 32是零，有的机器上1 << 32是非零（移位的位数%（取模）变量的宽度）。上述代码预期在这种情况下，1 << 32是零。
   为了保证程序的可移植性，需要程序员保证移位数的取值范围是[0, w)。
2. 修改代码，使得它在int至少为32位的机器上都能正确地运行。

int int_size_is_32()
{int set_msb = 1 << 31;int beyond_msb = set_msb << 1;  // 确保在不同的机器上，程序的行为是一致的。// set_msb非零时，int_size >= 32；beyond_msb为零时，int_size <= 32return set_msb && !beyond_msb;  
}

3. 修改代码，使得它在int至少为16位的机器上都能正确地运行。

int int_size_is_32()
{int set_msb = 1 << 15 << 15 << 1;  // 保证左移行为符合预期int beyond_msb = set_msb << 1;// set_msb非零时，int_size >= 32；beyond_msb为零时，int_size <= 32return set_msb && !beyond_msb;  
}

2.68**

问：实现一个函数，输入正整数n$(1\le n\le w)$，返回低n位均为1的掩码值。如输入6返回0x3F，输入17返回0x1FFFF。
答：

int lower_one_mask(int n)
{return (unsigned)-1 >> ((sizeof(int) << 3) - n);
}

在x86_64机器上的运行结果：

// printf("%d\n", lower_one_mask(0));
// printf("%p\n", lower_one_mask(6));
// printf("%p\n", lower_one_mask(17));
// printf("%p\n", lower_one_mask(31));
// printf("%p\n", lower_one_mask(32));
[liheng@localhost2 2]$ ./a.out 
0
0x3f
0x1ffff
0x7fffffff
0xffffffff

2.69***

问：实现循环左移，$0\le n<w$。如x = 0x12345678、w = 32，n = 4返回0x23456781，n = 20返回0x67812345。
答：

unsigned rotate_left(unsigned x, int n)
{unsigned low = x >> ((sizeof(unsigned) << 3) - n);unsigned high = x << n;return high | low;
}

在x86_64机器上的运行结果：

// printf("%p\n", rotate_left(0x12345678, 0));
// printf("%p\n", rotate_left(0x12345678, 4));
// printf("%p\n", rotate_left(0x12345678, 8));
// printf("%p\n", rotate_left(0x12345678, 12));
// printf("%p\n", rotate_left(0x12345678, 16));
// printf("%p\n", rotate_left(0x12345678, 20));
// printf("%p\n", rotate_left(0x12345678, 24));
// printf("%p\n", rotate_left(0x12345678, 28));
// printf("%p\n", rotate_left(0x12345678, 31));
[liheng@localhost2 2]$ ./a.out 
0x12345678
0x23456781
0x34567812
0x45678123
0x56781234
0x67812345
0x78123456
0x81234567
0x91a2b3c

2.70**

问：实现一个函数，如果x能被表示成n位$(1\le n\le w)$的二进制补码，就返回1，否则返回0。
答：

int fits_bits(int x, int n)
{int w = sizeof(int) << 3;int offset = w - n;return ((x << offset) >> offset) == x;  // 如果x不能用n个比特位表示，移位操作会使它丢失最高的有效位
}

在x86_64机器上的运行结果：

// printf("%d\n", fits_bits(-4, 3));
// printf("%d\n", fits_bits(3, 3));
// printf("%d\n", fits_bits(-5, 3));
// printf("%d\n", fits_bits(4, 3));
[liheng@localhost2 2]$ ./a.out 
1
1
0
0

2.71*

问：packed_t类型是将4个有符号字节封装成一个32位的unsigned，字节从0（最低有效字节）编码到3最高有效字节。有如下一个函数xbyte，提取出特定的字节，再把它符号扩展成一个int。

typedef unsigned packed_t;
int xbyte(packed_t word, int byteNum)
{return (word >> (byteNum << 3)) & 0xFF;
}

答：

1. 写上述代码的人被解雇了，这段代码错在哪里？
   编译器会把(word >> (byteNum << 3)) & 0xFF的结果当作无符号数，扩展时使用零扩展而非符号扩展。

// printf("%d\n", xbyte(-1, 3));
[liheng@localhost2 2]$ ./a.out 
255

2. 给出函数的正确实现。

typedef unsigned packed_t;
int xbyte(packed_t word, int byteNum)
{return (int8_t)((word >> (byteNum << 3)) & 0xFF);  // 把结果转成有符号数
}

在x86_64机器上的运行结果：

// printf("%d\n", xbyte(-1, 3));
[liheng@localhost2 2]$ ./a.out 
-1

2.72**

问：下面的函数将整数val复制到缓冲区buf中。

void copy_int(int val, void *buf, int maxbytes)
{if (maxbytes - sizeof(val) >= 0) {memcpy(buf, &val, sizeof(val));}
}

答：

1. sizeof的返回值类型是size_t，这段代码存在什么问题？
   size_t是无符号类型unsigned的别名，maxbytes是有符号数，无符号数和有符号数运算时，结果是无符号数（永远$\ge 0$），因此if分支的判断语句永远为true。memcpy会造成缓冲区的写溢出。
2. 改正代码。

void copy_int(int val, void *buf, int maxbytes)
{if (maxbytes >= sizeof(val) {  // 无符号数之间的比较memcpy(buf, &val, sizeof(val));}
}

2.73**

问：实现饱和加法：正溢出时返回TMax，负溢出时返回TMin。
答：

int saturating_add(int x, int y)
{int s = x + y;int mask = 1 << ((sizeof(int) << 3) - 1);int neg_overflow = (x & mask) && (y & mask) && !(s & mask);int pos_overflow = !(x & mask) && !(y & mask) && (s & mask);(neg_overflow && (s = INT_MIN)) || (pos_overflow && (s = INT_MAX));return s;
}

在x86_64机器上的运行结果：

// printf("%d\n", saturating_add(123, 456));
// printf("%d\n", saturating_add(-123, -456));
// printf("%d\n", saturating_add(INT_MAX, 123));
// printf("%d\n", saturating_add(INT_MIN, -123));
[liheng@localhost2 2]$ ./a.out 
579
-579
2147483647
-2147483648

2.74**

问：实现一个函数，两数相减不溢出就返回1，否则返回0。
答：

int tsub_ok(int x, int y)
{int s = x - y;return !((x > 0 && y < 0 && s < 0) || (x < 0 && y > 0 && s > 0));
}

在x86_64机器上的运行结果：

// printf("%d\n", tsub_ok(-1, 3));
// printf("%d\n", tsub_ok(INT_MIN, 1));
// printf("%d\n", tsub_ok(INT_MAX, -1));
[liheng@localhost2 2]$ ./a.out 
1
0
0

正常情况：正数+正数=正数；溢出情况：正数+正数=负数。
正常情况：负数+负数=负数；溢出情况：负数+负数=正数。
正常情况：正数-负数=正数；溢出情况：正数-负数=负数。
正常情况：负数-正数=负数；溢出情况：负数-正数=正数。

2.75***

问：假设我们要计算x * y的完整的2w位表示，其中x和y都是无符号数，并且w=32，乘积的低w位能够用表达式x * y计算。所以我们只需要额外计算它的高w位，声明如下：

unsigned unsigned_high_prod(unsigned x, unsigned y);

我们使用一个库函数，它计算在x和y采用补码形式的情况下，x * y的高w位。声明如下：

int signed_high_prod(int x, int y);

编写代码调用signed_high_prod，实现unsigned_high_prod。

答：
假设x和y是无符号数，$x^{\prime }$和$y^{\prime }$分别是它们的补码数。有$x=x^{\prime }+x_{w-1}{2}^w$、$y=y^{\prime }+y_{w-1}{2}^w$，因此
$$x\ast y=(x^{\prime }+x_{w-1}{2}^w)\ast (y^{\prime }+y_{w-1}{2}^w)=x^{\prime }\ast y^{\prime }+(x^{\prime }{y}_{w-1}+y^{\prime }{x}_{w-1})2^w+x_{w-1}{y}_{w-1}{2}^{2w}$$
取低2w位，结果是$x^{\prime }\ast y^{\prime }+(x^{\prime }{y}_{w-1}+y^{\prime }{x}_{w-1})2^w$，获取其中的高w位的实现如下：

unsigned unsigned_high_prod(unsigned x, unsigned y)
{int a = signed_high_prod(x, y);return a + x * (y >> 31) + y * (x >> 31);
}

2.76*

问：
库函数calloc声明如下：

void *calloc(size_t nmemb, size_t size);

函数calloc为一个数组分配内存，并将内存设置为0。该数组有nmemb个元素，每个元素的大小为size字节。如果nmemb或size为0，calloc返回NULL。
编写calloc的实现，通过malloc分配内存，再通过memset将内存设置为0。你的代码应该没有任何由算术溢出引起的漏洞，且无论size_t用多少位表示，代码都应该正常工作。malloc和memset的声明如下：

void *malloc(size_t size);
void *memset(void *s, inc c, size_t n);

答：
calloc的实现如下：

void *calloc(size_t nmemb, size_t size)
{size_t bytes = nmemb * size;if ((bytes == 0) || (bytes / nmemb != size)) {  // 分配0字节或溢出return NULL;}void *addr = malloc(bytes);if (addr == NULL) {return NULL;}return memset(addr, 0x00, bytes);
}