CSAPP3e 第二章家庭作业（1）

Author： tomaito
发布时间：September 26, 2020
695views
No comments
6543 words
Categories： csapp

CSAPP第二章家庭作业(课后习题)(Homework)2.58-2.80。

Homework of chapter 2

2.58

判断系统是否为小端存储方式

/**
 * @author ccl
 * 判断系统是否为小端存储方式
 */
int is_little_endian() {
    static long val = 1;
    return *(char * ) &val == 1;
}

2.59

编写一个C表达式，它生成一个字，由x的最低有效字节和y中剩下的字节组成。对于运算数x=0x89ABCDEF 和 y=0x76543210, 就得到0x765432EF 。

#define MASK 0xFF
#define generate_word( x , y ) ((x & MASK) | (y& (~MASK) ))

2.60

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

unsigned replace_byte ( unsigned x , int i , unsigned char b ) {
    /* u 代表无符号类型 */
    unsigned mask = ~ ( 0xFFu << ( i << 3 ) );
    unsigned rb = ( unsigned ) b << ( i << 3 );
    return ( x & mask ) | rb;
}

2.61

x 的每一位都等于1：!~x。
x 的每一位都等于0：!x。
x 的最低有效字节中的位都等于1
x 的最高有效字节中的位都等于0

#define MASK 0xFF

#define A( x ) (!(~x))
#define B( x ) (!x)

int C ( int x ) {
    return ( x & MASK ) == MASK;
}

int D ( int x ) {
    int shift = ( sizeof ( int ) - 1 ) << 3;
    return ! ( ( x >> shift ) & MASK );
}

2.62

编写函数 int_shifts_are_arithmetic() ，在对 int 类型的数使用算术右移的机器上生成1，反之生成0。要求在任意字长的机器上都可以运行。

int int_shifts_are_arithemetic(){
    int x = ~0;
    return !(x ^ (x >> 1));
}

2.63

函数 srl() 用算术右移来完成逻辑右移。函数 sra() 用逻辑右移来完成算术右移。不能使用右移或除法。

/**
 * 用逻辑右移实现算术右移
 * 将xsra的高k位置零即可
 */
unsigned srl ( unsigned x , int k ) {
    unsigned xsra = ( int ) x >> k;
    /* 将 xsra 的高k位置零 */
    int w = sizeof ( x ) << 3;
    unsigned mask = ~ ( ( (int) -1 ) << ( w - k ) );
    return xsra & mask;
}

/**
 * 用算术右移实现逻辑右移
 * 如果x >= 0, 答案就是xsrl
 * 如果x < 0, 将xsrl的高k位置1
 */
int sra ( int x , int k ) {
    int xsrl = ( unsigned ) x >> k;
    int w = sizeof ( x ) << 3;

    /* 构造一个mask, 如果x >= 0, mask = 0; 否则mask的高k位为1 */
    unsigned mask = ( ( (int) -1 ) << ( w - k ) ) ;
    int msb = ( x & (1 << (w - 1)) );
    mask &= (!msb) - 1;
    return xsrl | mask;
}

2.64

编写函数 any_odd _one(x) ，当 x 的二进制表示中的任一奇数位都为1时返回1，否则返回0。假设 w=32。

/**
 * Return 1 when any odd bit of x equals 1; 0 otherwise. Assume w=32
 */
int any_odd_one(unsigned x){
    /* 假设最低位为第0位 */
    return (x & 0xAAAAAAAA) != 0;
}

2.65

编写函数 odd_ones(x) ，当 x 的二进制表达含有奇数个1时返回1，否则返回零。设 w=32w=32。代码中算术运算、位运算和逻辑运算最多只能包含12个。

/**
 * Return 1 when x contains an odd number of 1s; 0 otherwise. Assume w=32.
 * 通过不断的异或来消除偶数个1
 */
int odd_ones ( unsigned x ) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 0x1;
}

2.66

生成一个掩码，取 x 的最高非零位。假设 w=32。最多只能包含15个算术运算、位级运算和逻辑运算。

/*
 * Generate mask indicating leftmost 1 in x. Assume w=32
 * For example, 0xFF00 -> 0x8000, and 0x6000 -> 0x4000.
 * If x = 0, then return 0
 */
int leftmost_one(unsigned x){
    /* 将x的最高非零位至最低为都置为1. 如 0x6000 -> 0x7FFF
     * 然后取 x ^ (x >> 1)就能将最高位后的所有1置0
     */
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x ^ (x >> 1);
}

2.67

编写一个过程 int_size_is_32() ，当在一个 int 是32位的机器上运行时产生1，而其他情况则产生0。不允许使用 sizeof 运算符。下面是一个错误的尝试：

int bad_int_size_is_32 () {
    int set_msb = 1 << 31;
    int beyond_msb = 1 << 32;
    return set_msb && ! beyond_msb;
}

请回答：
这份代码在哪个方面没有遵守 C 语言标准？
修改代码使得它在 int 至少为32位的任何机器上都能正确地运行。
修改代码使得它在 int 至少为16位的任何机器上都能正确地运行。

当int位32位时，左移32位超过了最大左移宽度，实际为 1 << (32 % 32) = 1 << 0 = 1

/**
 * 判断 int 是否为32位
 * 该函数在 int 至少为32位的任何机器上都能正确地运行。
 */
int int_size_is_32 () {
    int set_msb = 1 << 31;
    int beyond_msb = set_msb << 1;
    return set_msb && ! beyond_msb;
}

/**
 * 判断 int 是否为32位
 * 该函数在 int 至少为16位的任何机器上都能正确地运行。
 */
int int_size_is_32_in16 () {
    /* 由于int可能为16位，因此最多只能左移15位 */
    int set_msb = ( ( 1 << 15 ) << 15 ) << 1;
    int beyond_msb = set_msb << 1;
    return set_msb && ! beyond_msb;
}

2.68

编写一个函数，生成一个掩码，将其最低 n 位置为 1 。其中 1 ≤ n ≤ w 。注意 n=w 的情况。

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

2.69

将x循环左移n位. Examples when x = 0x12345678 and w = 32. n=4 -> 0x23456781, n=20 -> 0x67812345.

/**
 * Do rotating left shift. Assume O <= n < w
 * Examples when x = 0x12345678 and w = 32:
 * n=4 -> 0x23456781, n=20 -> 0x67812345
 * 循环左移n位
*/
unsigned rotate_left(unsigned x, int n){
    int w = sizeof(int) << 3;
    return x << n | (x >> (w - n - 1) ) >> 1  ;
}

2.70

编写一个函数，当 x 可以被表示为 n 位补码时返回1，否则返回0。其中 $1≤n≤w$ 。

/**
 * 例如n=8, 从截断的角度考虑.
 * int转为char值不变, 即 (char)x == x;
 * 对于任意的n，将x截断为n位后仍然和x相等，那么x就能用n位的二进制补码表示
 * 截断为n位就是 x << (w - n) >> (w - n)。(算术右移，不会改变原来的值)
 */
int fits_bits_1 ( int x , int n ) {
    int w = sizeof ( x ) << 3;
    int t = ( ( x << ( w - n ) ) >> ( w - n ) );
    return t == x;
}

/**
 * 再次的观察后可发现，x 能用 n 位的二进制补码表示的条件为
 * x 的前 w - n + 1 位要么全为 1, 要么全为 0.
 */
int fits_bits_2 ( int x , int n ) {
    int t = x >> ( n - 1 );
    return ! t || ! ~ t;
}

/**
 * 函数是正确的，但不符合条件，可以用于对拍。
 */
int fits_bits_3 ( int x , int n ) {
    int low = - ( 1U << ( n - 1 ) );
    int up = ( 1U << ( n - 1 ) ) - 1;
    return x >= low && x <= up;
}

2.71

从一个数x中提取一个字节，然后将其符号扩展为int。

typedef unsigned packet_t;

/**
 * Extract byte from word. Return as signed integer.
 */
int xbyte ( packet_t word , int bytenum ) {
    int w = sizeof ( word );
    int shift = ( w - 1 - bytenum ) << 3;
    /* 先将待提取的字节移到最高位，然后算术右移即可 */
    int x = word << shift;
    return x >> ( ( w - 1 ) << 3 );
}

2.72

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

2.73

实现饱和加法，将两个 int 类型的数 x 和 y 相加，若正溢出返回 INT_MAX ，负溢出返回 INT_MIN ，无溢出返回其和。

#include <limits.h>

int saturating_add(int x, int y) {
    int sum = x + y;
    int sig_mask = INT_MIN;
    /*
     * if x > 0, y > 0 but sum < 0, it's a positive overflow
     * if x < 0, y < 0 but sum >= 0, it's a negative overflow
     */
    int pos_over = !(x & sig_mask) && !(y & sig_mask) && (sum & sig_mask);
    int neg_over = (x & sig_mask) && (y & sig_mask) && !(sum & sig_mask);

    (pos_over && (sum = INT_MAX) || neg_over && (sum = INT_MIN));

    return sum;
}

2.74

编写函数 tsub_ok(int x, int y) 来检测 x − y 是否溢出。

#include <limits.h>
int tsub_ok(int x, int y){
    int sub = x - y;
    int sig_mask = INT_MIN;
    /*
     * pay attention to the case: (0 - INT_MIN)
     * if x >= 0, y < 0 but sum < 0, it's a positive overflow.
     * if x < 0, y >= 0 but sum >= 0, it's a negative overflow.
     */
    int pos_over = !(x & sig_mask) && (y & sig_mask) && (sub & sig_mask);
    int neg_over = (x & sig_mask) && !(y & sig_mask) && !(sub & sig_mask);
    return !pos_over && !neg_over;
}

2.75

已知有函数 int signed_high_prod(int x, int y) 计算整型变量 x 和 y 相乘后高 $w$ 位的值。请编写 unsigned unsigned_high_prod(unsigned x, unsigned y) 来计算无符号型变量相乘后高 $w$ 位的值。

设$x′$ 和 $y′$ 分别是 x 和 y 的无符号类型值. 书上的公式2-18如下

$$ x' * y' = x*y + (x_{w-1}*y + y_{w-1}*x)*2^w + (x_{w-1}*y_{w-1})*2^{2w}$$

由于取得是高w位，因此一个数乘于$2^w$, 那么这个数就处于高$w$位中。同时$2^{2w}$不会改变位的表示.

因此答案就是 $\text{signed_high_prod(x, y)} + x_{w-1}*y + y_{w-1}*x$

unsigned unsigned_high_prod ( unsigned x , unsigned y ) {
    int w = sizeof(x) << 3;
    int sign_x = x >> ( w - 1 ) ;    // x_{w-1}
    int sign_y = y >> ( w - 1 ) ;    // y_{w-1}

    /* 后面两个乘法不用可以不用加(int)y * sign_x， sign_x要么为0要么为1 */
    return signed_high_prod ( ( int ) x , ( int ) y ) + y * sign_x + x * sign_y;
}

/**
 * 下面两个函数用于对拍
 */
int signed_high_prod( int x, int y) {
    int64_t mul = (int64_t) x * y;
    return mul >> 32;
}


unsigned another_unsigned_high_prod(unsigned x, unsigned y) {
    uint64_t mul = (uint64_t) x * y;
    return mul >> 32;
}

2.76

库函数 calloc 有如下声明：void *calloc(size_t nmemb, size_t size); 。根据库文档：“函数 calloc 为一个数组分配内存，该数组有 nmemb 个元素，每个元素为 size 字节。内存设置为0。如果 nmemb 或 size 为0，则 calloc 返回 NULL 。”
编写 calloc 的实现，通过调用 malloc 执行分配，调用 memset 将内存设置为0。你的代码应该没有任何由算术溢出引起的漏洞，且无论数据类型 size_t 用多少位表示，代码都应该正常工作。
作为参考，函数 malloc 和 memset 声明如下：
void *malloc(size_t size);
void *memset(void *s, int c, size_t n);

判断乘法是否溢出即可.

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

void *calloc(size_t nmemb, size_t size) {
    if(nmemb == 0 || size == 0) {
        return NULL;
    }
    int sz = nmemb * size ;
    if(sz / nmemb == size) // 乘法没有溢出
    {
        void* ptr = malloc(sz);
        if(ptr != NULL) {
            memset(ptr, 0, sz);
        }
        return ptr;
    }

    return NULL;
}

2.77

假设我们有一个任务：生成一段代码，将整数变量 x 乘以不同的常数因子 K 。为了提高效率，我们想只使用 + - << 运算。对于下列 K 的值，写出执行乘法运算的 C 表达式，每个表达式中最多使用 3 个运算。
A. K=17
B. K=−7
C. K=60
D. K=−112

(x << 4) + x
x - (x << 3)
(x << 6) - (x << 2)
(x << 4) - (x << 7)

2.78

写出具有如下原型的函数的代码：
/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k);

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k) {
    int w = sizeof(int) << 3;
    int neg = x >> (w - 1);
    neg && (x += (1 << k) - 1);
    return x >> k;
}

2.79

写出函数 mul3div4 的代码，对于整数参数x, 计算3 x / 4, 但是要遵循位级整数编码规则。你的代码计算3x 也会产生溢出。

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k) {
    int neg = x & INT_MIN;
    neg && (x += (1 << k) - 1);
    return x >> k;
}

int mul3div4(int x) {
    x = (x << 1) + x ;
    return divide_power2 (x, 2);
}

2.80

写出函数 threefourths 的代码。对于整数参数 x ，计算 $\frac{3}{4}x$ 的值，向零舍入。它不会溢出。函数应该遵循位级整数编码规则。

不溢出就需要先除以4，然后再乘于3，但是先出4再乘3就不对了，尾部的小数字原本在左移后是可以进位的，但是在右移的过程中会直接舍去！解决方法是将x分为两部分，前30位和后2位，分开计算再求和。

former = x & ~0x3
later = x & 0x3
x = former + later
threefourths(x) = former/4*3 + later*3/4

former能被4整除，因此不会出现精度问题，later 无法被4整除，later 需要先乘3再除4.

#include <limits.h>

int threefourths(int x) {
    int former = x & ~0x3;
    int later = x & 0x3;

    /* former / 4 * 3 */
    former >>= 2;
    former = (former << 1) + former;

    /* later * 3 / 4 */
    later = (later << 1) + later;
    int neg = x & INT_MIN;
    neg && (later += (1 << 2) - 1);
    later >>= 2;

    return former + later;
}

Last modification：September 26th, 2020 at 07:46 pm

如果觉得我的文章对你有用，请随意赞赏

CSAPP3e 第二章家庭作业（1）

tomaito • 2020 年 09 月 26 日

CSAPP第二章家庭作业(课后习题)(Homework)2.58-2.80。

Homework of chapter 2

2.58

判断系统是否为小端存储方式

/**
 * @author ccl
 * 判断系统是否为小端存储方式
 */
int is_little_endian() {
    static long val = 1;
    return *(char * ) &val == 1;
}

2.59

编写一个C表达式，它生成一个字，由x的最低有效字节和y中剩下的字节组成。对于运算数x=0x89ABCDEF 和 y=0x76543210, 就得到0x765432EF 。

#define MASK 0xFF
#define generate_word( x , y ) ((x & MASK) | (y& (~MASK) ))

2.60

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

unsigned replace_byte ( unsigned x , int i , unsigned char b ) {
    /* u 代表无符号类型 */
    unsigned mask = ~ ( 0xFFu << ( i << 3 ) );
    unsigned rb = ( unsigned ) b << ( i << 3 );
    return ( x & mask ) | rb;
}

2.61

x 的每一位都等于1：!~x。
x 的每一位都等于0：!x。
x 的最低有效字节中的位都等于1
x 的最高有效字节中的位都等于0

#define MASK 0xFF

#define A( x ) (!(~x))
#define B( x ) (!x)

int C ( int x ) {
    return ( x & MASK ) == MASK;
}

int D ( int x ) {
    int shift = ( sizeof ( int ) - 1 ) << 3;
    return ! ( ( x >> shift ) & MASK );
}

2.62

编写函数 int_shifts_are_arithmetic() ，在对 int 类型的数使用算术右移的机器上生成1，反之生成0。要求在任意字长的机器上都可以运行。

int int_shifts_are_arithemetic(){
    int x = ~0;
    return !(x ^ (x >> 1));
}

2.63

函数 srl() 用算术右移来完成逻辑右移。函数 sra() 用逻辑右移来完成算术右移。不能使用右移或除法。

/**
 * 用逻辑右移实现算术右移
 * 将xsra的高k位置零即可
 */
unsigned srl ( unsigned x , int k ) {
    unsigned xsra = ( int ) x >> k;
    /* 将 xsra 的高k位置零 */
    int w = sizeof ( x ) << 3;
    unsigned mask = ~ ( ( (int) -1 ) << ( w - k ) );
    return xsra & mask;
}

/**
 * 用算术右移实现逻辑右移
 * 如果x >= 0, 答案就是xsrl
 * 如果x < 0, 将xsrl的高k位置1
 */
int sra ( int x , int k ) {
    int xsrl = ( unsigned ) x >> k;
    int w = sizeof ( x ) << 3;

    /* 构造一个mask, 如果x >= 0, mask = 0; 否则mask的高k位为1 */
    unsigned mask = ( ( (int) -1 ) << ( w - k ) ) ;
    int msb = ( x & (1 << (w - 1)) );
    mask &= (!msb) - 1;
    return xsrl | mask;
}

2.64

编写函数 any_odd _one(x) ，当 x 的二进制表示中的任一奇数位都为1时返回1，否则返回0。假设 w=32。

/**
 * Return 1 when any odd bit of x equals 1; 0 otherwise. Assume w=32
 */
int any_odd_one(unsigned x){
    /* 假设最低位为第0位 */
    return (x & 0xAAAAAAAA) != 0;
}

2.65

编写函数 odd_ones(x) ，当 x 的二进制表达含有奇数个1时返回1，否则返回零。设 w=32w=32。代码中算术运算、位运算和逻辑运算最多只能包含12个。

/**
 * Return 1 when x contains an odd number of 1s; 0 otherwise. Assume w=32.
 * 通过不断的异或来消除偶数个1
 */
int odd_ones ( unsigned x ) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 0x1;
}

2.66

生成一个掩码，取 x 的最高非零位。假设 w=32。最多只能包含15个算术运算、位级运算和逻辑运算。

/*
 * Generate mask indicating leftmost 1 in x. Assume w=32
 * For example, 0xFF00 -> 0x8000, and 0x6000 -> 0x4000.
 * If x = 0, then return 0
 */
int leftmost_one(unsigned x){
    /* 将x的最高非零位至最低为都置为1. 如 0x6000 -> 0x7FFF
     * 然后取 x ^ (x >> 1)就能将最高位后的所有1置0
     */
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x ^ (x >> 1);
}

2.67

编写一个过程 int_size_is_32() ，当在一个 int 是32位的机器上运行时产生1，而其他情况则产生0。不允许使用 sizeof 运算符。下面是一个错误的尝试：

int bad_int_size_is_32 () {
    int set_msb = 1 << 31;
    int beyond_msb = 1 << 32;
    return set_msb && ! beyond_msb;
}

请回答：
这份代码在哪个方面没有遵守 C 语言标准？
修改代码使得它在 int 至少为32位的任何机器上都能正确地运行。
修改代码使得它在 int 至少为16位的任何机器上都能正确地运行。

当int位32位时，左移32位超过了最大左移宽度，实际为 1 << (32 % 32) = 1 << 0 = 1

/**
 * 判断 int 是否为32位
 * 该函数在 int 至少为32位的任何机器上都能正确地运行。
 */
int int_size_is_32 () {
    int set_msb = 1 << 31;
    int beyond_msb = set_msb << 1;
    return set_msb && ! beyond_msb;
}

/**
 * 判断 int 是否为32位
 * 该函数在 int 至少为16位的任何机器上都能正确地运行。
 */
int int_size_is_32_in16 () {
    /* 由于int可能为16位，因此最多只能左移15位 */
    int set_msb = ( ( 1 << 15 ) << 15 ) << 1;
    int beyond_msb = set_msb << 1;
    return set_msb && ! beyond_msb;
}

2.68

编写一个函数，生成一个掩码，将其最低 n 位置为 1 。其中 1 ≤ n ≤ w 。注意 n=w 的情况。

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

2.69

将x循环左移n位. Examples when x = 0x12345678 and w = 32. n=4 -> 0x23456781, n=20 -> 0x67812345.

/**
 * Do rotating left shift. Assume O <= n < w
 * Examples when x = 0x12345678 and w = 32:
 * n=4 -> 0x23456781, n=20 -> 0x67812345
 * 循环左移n位
*/
unsigned rotate_left(unsigned x, int n){
    int w = sizeof(int) << 3;
    return x << n | (x >> (w - n - 1) ) >> 1  ;
}

2.70

编写一个函数，当 x 可以被表示为 n 位补码时返回1，否则返回0。其中 $1≤n≤w$ 。

/**
 * 例如n=8, 从截断的角度考虑.
 * int转为char值不变, 即 (char)x == x;
 * 对于任意的n，将x截断为n位后仍然和x相等，那么x就能用n位的二进制补码表示
 * 截断为n位就是 x << (w - n) >> (w - n)。(算术右移，不会改变原来的值)
 */
int fits_bits_1 ( int x , int n ) {
    int w = sizeof ( x ) << 3;
    int t = ( ( x << ( w - n ) ) >> ( w - n ) );
    return t == x;
}

/**
 * 再次的观察后可发现，x 能用 n 位的二进制补码表示的条件为
 * x 的前 w - n + 1 位要么全为 1, 要么全为 0.
 */
int fits_bits_2 ( int x , int n ) {
    int t = x >> ( n - 1 );
    return ! t || ! ~ t;
}

/**
 * 函数是正确的，但不符合条件，可以用于对拍。
 */
int fits_bits_3 ( int x , int n ) {
    int low = - ( 1U << ( n - 1 ) );
    int up = ( 1U << ( n - 1 ) ) - 1;
    return x >= low && x <= up;
}

2.71

从一个数x中提取一个字节，然后将其符号扩展为int。

typedef unsigned packet_t;

/**
 * Extract byte from word. Return as signed integer.
 */
int xbyte ( packet_t word , int bytenum ) {
    int w = sizeof ( word );
    int shift = ( w - 1 - bytenum ) << 3;
    /* 先将待提取的字节移到最高位，然后算术右移即可 */
    int x = word << shift;
    return x >> ( ( w - 1 ) << 3 );
}

2.72

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

2.73

实现饱和加法，将两个 int 类型的数 x 和 y 相加，若正溢出返回 INT_MAX ，负溢出返回 INT_MIN ，无溢出返回其和。

#include <limits.h>

int saturating_add(int x, int y) {
    int sum = x + y;
    int sig_mask = INT_MIN;
    /*
     * if x > 0, y > 0 but sum < 0, it's a positive overflow
     * if x < 0, y < 0 but sum >= 0, it's a negative overflow
     */
    int pos_over = !(x & sig_mask) && !(y & sig_mask) && (sum & sig_mask);
    int neg_over = (x & sig_mask) && (y & sig_mask) && !(sum & sig_mask);

    (pos_over && (sum = INT_MAX) || neg_over && (sum = INT_MIN));

    return sum;
}

2.74

编写函数 tsub_ok(int x, int y) 来检测 x − y 是否溢出。

#include <limits.h>
int tsub_ok(int x, int y){
    int sub = x - y;
    int sig_mask = INT_MIN;
    /*
     * pay attention to the case: (0 - INT_MIN)
     * if x >= 0, y < 0 but sum < 0, it's a positive overflow.
     * if x < 0, y >= 0 but sum >= 0, it's a negative overflow.
     */
    int pos_over = !(x & sig_mask) && (y & sig_mask) && (sub & sig_mask);
    int neg_over = (x & sig_mask) && !(y & sig_mask) && !(sub & sig_mask);
    return !pos_over && !neg_over;
}

2.75

已知有函数 int signed_high_prod(int x, int y) 计算整型变量 x 和 y 相乘后高 $w$ 位的值。请编写 unsigned unsigned_high_prod(unsigned x, unsigned y) 来计算无符号型变量相乘后高 $w$ 位的值。

设$x′$ 和 $y′$ 分别是 x 和 y 的无符号类型值. 书上的公式2-18如下

$$ x' * y' = x*y + (x_{w-1}*y + y_{w-1}*x)*2^w + (x_{w-1}*y_{w-1})*2^{2w}$$

由于取得是高w位，因此一个数乘于$2^w$, 那么这个数就处于高$w$位中。同时$2^{2w}$不会改变位的表示.

因此答案就是 $\text{signed_high_prod(x, y)} + x_{w-1}*y + y_{w-1}*x$

unsigned unsigned_high_prod ( unsigned x , unsigned y ) {
    int w = sizeof(x) << 3;
    int sign_x = x >> ( w - 1 ) ;    // x_{w-1}
    int sign_y = y >> ( w - 1 ) ;    // y_{w-1}

    /* 后面两个乘法不用可以不用加(int)y * sign_x， sign_x要么为0要么为1 */
    return signed_high_prod ( ( int ) x , ( int ) y ) + y * sign_x + x * sign_y;
}

/**
 * 下面两个函数用于对拍
 */
int signed_high_prod( int x, int y) {
    int64_t mul = (int64_t) x * y;
    return mul >> 32;
}


unsigned another_unsigned_high_prod(unsigned x, unsigned y) {
    uint64_t mul = (uint64_t) x * y;
    return mul >> 32;
}

2.76

库函数 calloc 有如下声明：void *calloc(size_t nmemb, size_t size); 。根据库文档：“函数 calloc 为一个数组分配内存，该数组有 nmemb 个元素，每个元素为 size 字节。内存设置为0。如果 nmemb 或 size 为0，则 calloc 返回 NULL 。”
编写 calloc 的实现，通过调用 malloc 执行分配，调用 memset 将内存设置为0。你的代码应该没有任何由算术溢出引起的漏洞，且无论数据类型 size_t 用多少位表示，代码都应该正常工作。
作为参考，函数 malloc 和 memset 声明如下：
void *malloc(size_t size);
void *memset(void *s, int c, size_t n);

判断乘法是否溢出即可.

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

void *calloc(size_t nmemb, size_t size) {
    if(nmemb == 0 || size == 0) {
        return NULL;
    }
    int sz = nmemb * size ;
    if(sz / nmemb == size) // 乘法没有溢出
    {
        void* ptr = malloc(sz);
        if(ptr != NULL) {
            memset(ptr, 0, sz);
        }
        return ptr;
    }

    return NULL;
}

2.77

假设我们有一个任务：生成一段代码，将整数变量 x 乘以不同的常数因子 K 。为了提高效率，我们想只使用 + - << 运算。对于下列 K 的值，写出执行乘法运算的 C 表达式，每个表达式中最多使用 3 个运算。
A. K=17
B. K=−7
C. K=60
D. K=−112

(x << 4) + x
x - (x << 3)
(x << 6) - (x << 2)
(x << 4) - (x << 7)

2.78

写出具有如下原型的函数的代码：
/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k);

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k) {
    int w = sizeof(int) << 3;
    int neg = x >> (w - 1);
    neg && (x += (1 << k) - 1);
    return x >> k;
}

2.79

写出函数 mul3div4 的代码，对于整数参数x, 计算3 x / 4, 但是要遵循位级整数编码规则。你的代码计算3x 也会产生溢出。

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k) {
    int neg = x & INT_MIN;
    neg && (x += (1 << k) - 1);
    return x >> k;
}

int mul3div4(int x) {
    x = (x << 1) + x ;
    return divide_power2 (x, 2);
}

2.80

写出函数 threefourths 的代码。对于整数参数 x ，计算 $\frac{3}{4}x$ 的值，向零舍入。它不会溢出。函数应该遵循位级整数编码规则。

former = x & ~0x3
later = x & 0x3
x = former + later
threefourths(x) = former/4*3 + later*3/4

former能被4整除，因此不会出现精度问题，later 无法被4整除，later 需要先乘3再除4.

#include <limits.h>

int threefourths(int x) {
    int former = x & ~0x3;
    int later = x & 0x3;

    /* former / 4 * 3 */
    former >>= 2;
    former = (former << 1) + former;

    /* later * 3 / 4 */
    later = (later << 1) + later;
    int neg = x & INT_MIN;
    neg && (later += (1 << 2) - 1);
    later >>= 2;

    return former + later;
}

Homework of chapter 2

2.58

2.59

2.60

2.61

2.62

2.63

2.64

2.65

2.66

2.67

2.68

2.69

2.70

2.71

2.72

2.73

2.74

2.75

2.76

2.77

2.78

2.79

2.80