c语言 sizeof(a-%3eb),CSAPP3e 第二章家庭作业（1）
Loading...
CSAPP第二章家庭作业(课后习题)(Homework)2.58-2.80。
## Homework of chapter 2
### 2.58
> 判断系统是否为小端存储方式
```c
/**
* @author ccl
* 判断系统是否为小端存储方式
*/
int is_little_endian() {
static long val = 1;
return *(char * ) &val == 1;
}
```
### 2.59
>编写一个C表达式，它生成一个字，由x的最低有效字节和y中剩下的字节组成。对于运算数x=0x89ABCDEF 和 y=0x76543210, 就得到0x765432EF 。
```c
#define MASK 0xFF
#define generate_word( x , y ) ((x & MASK) | (y& (~MASK) ))
```
### 2.60
> 假设我们将一个 w 位的字中的字节从0( 最低位)到w/8 - 1( 最高位)编号。写出下面 C 函数的代码，它会返回一个无符号值，其中参数 x 第 i 个字节被替换成字节 b:
```c
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
```c
#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。要求在任意字长的机器上都可以运行。
```c
int int_shifts_are_arithemetic(){
int x = ~0;
return !(x ^ (x >> 1));
}
```
### 2.63
> 函数 `srl()` 用算术右移来完成逻辑右移。函数 `sra()` 用逻辑右移来完成算术右移。不能使用右移或除法。
```c
/**
* 用逻辑右移实现算术右移
* 将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。
```c
/**
* 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个。**
```c
/**
* 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个算术运算、位级运算和逻辑运算。**
```c
/*
* 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` 运算符。下面是一个错误的尝试：
```c
int bad_int_size_is_32 () {
int set_msb = 1 << 31;
int beyond_msb = 1 << 32;
return set_msb && ! beyond_msb;
}
```
> 请回答：
>
> 1. 这份代码在哪个方面没有遵守 C 语言标准？
> 1. 修改代码使得它在 `int` 至少为32位的任何机器上都能正确地运行。
> 1. 修改代码使得它在 `int` 至少为16位的任何机器上都能正确地运行。
1. 当int位32位时，左移32位超过了最大左移宽度，实际为 1 << (32 % 32) = 1 << 0 = 1
2.
```c
/**
* 判断 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;
}
```
3.
```
/**
* 判断 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 的情况。
```c
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.
```c
/**
* 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$ 。
```c
/**
* 例如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。
```c
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
```c
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` ，无溢出返回其和。
```c
#include
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 是否溢出。
```c
#include
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$
```c
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;
}
```
```c
/**
* 下面两个函数用于对拍
*/
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);`
判断乘法是否溢出即可.
```c
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 。为了提高效率，我们想只使用 `+` `-` `<
>
> - 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
> 写出具有如下原型的函数的代码：
>
> ```c
> /* Divide by power of 2. Assume 0 <= k < w-1 */
> int divide_power2(int x, int k);
> ```
```c
/* 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, 但是要遵循位级整数编码规则。你的代码计算3*x 也会产生溢出。
```c
/* 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位，分开计算再求和。
```c
former = x & ~0x3
later = x & 0x3
x = former + later
threefourths(x) = former/4*3 + later*3/4
```
`former`能被4整除，因此不会出现精度问题，`later` 无法被4整除，`later` 需要先乘3再除4.
```c
#include
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;
}
```
最后修改：2020 年 09 月 26 日 07 : 46 PM
© 允许规范转载
赞赏
如果觉得我的文章对你有用，请随意赞赏
×Close
赞赏作者
扫一扫支付
支付宝支付
微信支付