CSAPP hw2

2.55

#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for(i=0;i<len;i++) printf(" %.2x",start[i]);
    printf("\n");
}
void show_int(int x) {show_bytes((byte_pointer)&x,sizeof(int));}
void show_float(float x) {show_bytes((byte_pointer)&x,sizeof(int));}
void show_pointer(void *x) {show_bytes((byte_pointer)&x,sizeof(void *));}
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);
}
int main()
{
    test_show_bytes(12345);
    return 0;
}

小端法。

2.56

100
 64 00 00 00
 00 00 c8 42
 cc fd 61 00 00 00 00 00
-1
 ff ff ff ff
 00 00 80 bf
 cc fd 61 00 00 00 00 00
0
 00 00 00 00
 00 00 00 00
 cc fd 61 00 00 00 00 00

一个有趣的现象是它们的指针都是相同的。

2.57

#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for(i=0;i<len;i++) printf(" %.2x",start[i]);
    printf("\n");
}
void show_int(int x) {show_bytes((byte_pointer)&x,sizeof(int));}
void show_float(float x) {show_bytes((byte_pointer)&x,sizeof(int));}
void show_pointer(void *x) {show_bytes((byte_pointer)&x,sizeof(void *));}
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;
    short sval=(short)ival;
    long lval=(long)ival;
    double dval=(double)ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
    show_short(sval);
    show_long(lval);
    show_double(dval);
}
int main()
{
    int x;scanf("%d",&x);
    test_show_bytes(x);
    return 0;
}

2.58

int is_little_endian()
{
    int a=1;
    byte_pointer p=(byte_pointer)&a;
    return p[0];
}

2.59

#include <stdio.h>
int main()
{
    int a,b;scanf("%x %x",&a,&b);
    int mask=0xff;
    printf("%x\n",((a&mask)|(b&(~mask))));
    return 0;
}

2.60

unsigned replace_byte(unsigned x,int i,unsigned char b)
{
    unsigned char *p=(unsigned char *)&x;
    p[i]=b;
    return x;
}

缺点是只适用于小端的机器。网上有一种普适的写法：

size_t replace_byte(unsigned x,int i,unsigned char b)
{
    size_t mask=((unsigned)0xff)<<(i<<3);
    return (x&(~mask))|(((unsigned)b)<<(i<<3));
}

2.61

!~x
!x
!~(x|~0xff)
!(x>>((sizeof(int)-1)<<3))

2.62

int int_shifts_are_arithmetic()
{
    int w=(sizeof(int))<<3;
    return (INT_MIN)>>(w-1)==-1;
}

更好的做法：

int int_shifts_are_arithmetic()
{
	int x=-1;
    return x==x>>3;
}

2.63

unsigned srl(unsigned x,int k)
{
    unsigned xsra=(int)x>>k;
    int w=8*sizeof(int);
    int mask=(-1)<<(w-k);
    return xsra&(~mask);
}
int sra(int x,int k)
{
    int xsrl=(unsigned)x>>k;
    int w=8*sizeof(int);
    int mask=(-1)<<(w-k);
    int bit=x&(1<<(w-1));
    mask&=(!bit-1);
    return xsrl|mask;
}

2.64

int any_odd_one(unsigned x)
{
    return !!(x&0xaaaaaaaa);
}

2.65

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

没能想到。思路比较巧妙：最终 x 的最低位相当于是所有位异或起来的结果。

2.66

int leftmost_one(unsigned x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return (x >> 1) + (x && 1);	//(x && 1)用来解决x=0时的情况
}

同样巧妙：保证从第一次出现的 1 开始往后都是 1。然后右移再加 1 就是所要求的数了。

2.67

当 int 为 $32$ 位时，有效的移位位数为 $0\sim31$ 。代码中左移 $32$ 位是不合法的。

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_ng()
{
    int set_msb=1<<15;
    set_msb=set_msb<<15;
    set_msb=set_msb<<1;
    int beyond_msb=set_msb<<1;
    return set_msb&&!beyond_msb;
}

2.68

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

2.69

unsigned rotate_left(unsigned x,int n)
{
    unsigned mask=-1;
    int w=sizeof(int)<<3;
    mask<<=(w-n);
    int most=mask&x;
    x<<=n;
    most>>=(w-n);
    return most|x;
}

先保留 $x$ 的高 $n$ 位，然后和 $x$ 左移 $n$ 位得到的数拼起来。当然这里其实不需要使用掩码：

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

upd：以上两个做法都没有考虑到 $n=0$ 的情况，改进如下：

unsigned rotate_left(unsigned x,int n)
{
    unsigned w1=x<<n;
    unsigned w2=x>>1;
    w2>>=((sizeof(int)<<3)-n-1);
    return w1|w2;
}

2.70

int fits_bits(int x,int n)
{
    x>>=(n-1);
    return x==0||x==-1;
}

一个性质是，能够被表示的数满足：若该数为非负数，则高 $w-n+1$ 位均为 $0$ ，否则高 $w-n+1$ 位均为 $1$ 。

网上的写法：

int fits_bits(int x,int n)
{
    int w=sizeof(int)<<3;
    return x==x<<(w-n)>>(w-n);
}

相当于是剔除了多余的符号位。

2.71

未进行符号扩展。

typedef unsigned packed_t;
int xbyte(packed_t word,int bytenum)
{
    return ((int)(word<<((3-bytenum)<<3)))>>24;
}

2.72

size_t 为无符号，所以这里出现了有符号向无符号的隐式转换。而一个无符号的数始终大于等于 $0$ ，所以条件测试总是成功。

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

2.73

int saturating_add(int x, int y) {
  int sum=x+y;
  int sig_mask=INT_MIN;
  
  int pos_over=!(x & sig_mask) && !(y & sig_mask) && (sum & sig_mask);//x>0,y>0,正溢出
  int neg_over=(x & sig_mask) && (y & sig_mask) && !(sum & sig_mask);//x<0,y<0,负溢出
  
  pos_over && (sum = INT_MAX) || neg_over && (sum = INT_MIN);
  return sum;
}

避开 if 的一个小 trick。

2.74

int tsub_ok(int x,int y)
{
    int w=(sizeof(int)<<3)-1;
    int z=x-y;
    int pos_over=(x>>w)&&(!(y>>w))&&(!(z>>w));
    int neg_over=(!(x>>w))&&(y>>w)&&(z>>w);
    return !(pos_over||neg_over);
}

2.75

unsigned unsigned_high_prod(unsigned x,unsigned y)
{
    int w=(sizeof(int)<<3)-1;
    int a=x>>w,b=y>>w;
    return signed_high_prod(x,y)+a*y+b*x;
}

2.76

void *calloc(size_t nmemb,size_t size)
{
    if(!nmemb||!size) return NULL;
    size_t buf_size=nmemb*size;
    if(buf_size/size==nmemb)
    {
        void *p=malloc(buf_size);
        if(p!=NULL) memset(p,0,buf_size);
        return p;
    }   
    return NULL;
}

2.77

$(x<<4)+x$

$x-(x<<3)$

$(x<<6)-(x<<2)$

$(x<<4)-(x<<7)$

2.78

int divide_power2(int x,int k)
{
    int w=(sizeof(int)<<3);
    (x>>(w-1))&&(x+=((1<<k)-1));
    return x>>k;
}

利用短路避免了使用 if 或乘法，但感觉没什么意义啊（×

2.79

int mul3div4(int x)
{
    x=(x<<1)+x;
    return (x+((1<<2)-1)*(x<0))>>2; 
}

感觉题目要求翻译的怪怪的。和下一题对比来看，这道题目应该是允许溢出的（？不过这里用了乘法和比较，还是不太好，不如直接看下一题。

2.80

int mul3div4(int x)
{
    int y=x;
    int w=sizeof(int)<<3;
    (x>>(w-1))||(y+=3);
    return x-(y>>2);
}

一个小问题是 y+=3 仍然可能溢出，解决办法是对它进行判断，如果溢出则直接取减数为 y>>2+1 。

int mul3div4(int x)
{
    int y=x;
    int w=sizeof(int)<<3;
    (x>>(w-1))||(y+=3);
    int ans=x-(y>>2);
    !(x>>(w-1))&&!((y-3)>>(w-1))&&(y>>(w-1))&&(ans=x-((y-3)>>2)+1);
    return ans;
}

2.81

$-1<<k$

$(-1<<k)\oplus(-1<<(j+k))$

另一种方法是 $\sim(-1<<k)<<j$ 。

2.82

错误

$x=\mathrm{TMIN},y=0$

正确

\begin{aligned} &((x+y)<<4)+y-x\\ &=16(x+y)+y-x\\ &=17y+15x \end{aligned}

正确

\begin{aligned} &\sim x+\sim y+1\\ &=-x-1-y-1+1\\ &=-(x+y)-1\\ &=~(x+y) \end{aligned}

正确

2.83

$\dfrac{Y}{2^k-1}$

a) $\dfrac{5}{7}$

b) $\dfrac{2}{5}$

c) $\dfrac{19}{63}$

2.84

sx>sy||

(!sx&&!sy&&ux<=uy)||

(sx&&sy&&ux>=uy)||

(!(ux<<1)&&!(uy<<1))

2.85

	阶码	尾数	小数	值	位表示
A	$2$	$\frac{7}{4}$	$\frac{3}{4}$	$7$	100…1 1100…
B	$n$	$2-\frac{1}{2^n}$	$1-\frac{1}{2^n}$	$2^{n+1}-1$	100…11…1 11…1
C	$2^{k-1}-2$	$1$	$0$	$2^{2^{k-1}-2}$	11…0 00…0

2.86

	值	十进制
最小的正非规格化数	$2^{-16446}$	$1.8\times10^{-4951}$
最小的正规格化数	$2^{-16382}$	$3.4\times10^{-4932}$
最大的规格化数	$2^{16384}-2^{16320}$	$1.2\times10^{4932}$

2.87

	Hex	M	E	V	D
-0	8000	$0$	$-14$	$-0$	$-0.0$
最小的>2的值	4001	$\frac{1025}{1024}$	$1$	$\frac{1025}{512}$	$2.001953$
512	6000	$1$	$9$	$512$	$512.0$
最大的非规格化数	03FF	$\frac{1023}{1024}$	$-14$	$\frac{1023}{2^{-24}}$	$0.000061$
-∞	FC00	—	—	$-∞$	$-∞$
十六进制表示为3BB0的数	3BB0	$\frac{123}{64}$	$-1$	$\frac{123}{128}$	$0.960938$

2.88

208        0|1110|1010      208
-7/1024    1|0000|0111    -7/1024
5/2^17     0|0000|0001     1/2^10
-2^12      1|1110|1111      -248
768        0|1111|0000      +∞

2.89

正确。

int 向 double 转换不会损失精度，最终转成 float 的结果也一致。

错误。

$x=0,y=\mathrm{TMIN}$

错误。

$dx=0.001,dy=10^{300},dz=-10^{300}$

错误。

$dx=1.001,dy=10^{300},dz=10^{-300}$

$dx=1,dz=0$

2.90

-149

-126

(1<<(149+x))

128

x+127

255

2.91

11.0010010000111111011011

11.001(001)

小数点后第九位

2.92

float_bits float_negate(float_bits f)
{
    unsigned sign=f>>31;
    unsigned exp=f>>23&0xff;
    unsigned frac=f&0x7fffff;
    if(exp==0xff&&frac) return f;
    sign^=1;
    return (sign<<31)|(exp<<23)|frac;
}

奇怪的是如果使用 float，NAN 符号位会被翻转。这与题目中给出的要求不吻合。（不知道是不是测试出了什么bug还是版本问题）

2.93

typedef unsigned float_bits;
float_bits float_absval(float_bits f)
{
    unsigned sign=f>>31;
    unsigned exp=f>>23&0xff;
    unsigned frac=f&0x7fffff;
    if(exp==0xff&&frac) return f;
    sign=0;
    return (sign<<31)|(exp<<23)|frac; 
}

2.94

float_bits float_twice(float_bits f)
{
    unsigned sign=f>>31;
    unsigned exp=f>>23&0xff;
    unsigned frac=f&0x7fffff;
    if(exp==0xff&&frac!=0) return f;
    if(exp==0)
    {
        if(frac>>22)
        {
            exp++;
            frac=(frac<<1)&0x7fffff;
        }
        else frac=frac<<1;
    }   
    else
    {
        if(exp<255) exp++;
        if(exp==255) frac=0;
    }
    return (sign<<31)|(exp<<23)|frac;
}

剩下几道不想写了，感觉没什么意思，而且会有点麻烦（×

system

#CSAPP #位运算

CSAPP hw2

https://je3ter.github.io/2024/02/17/CSAPP/CSAPP hw2/

作者

Je3ter

发布于

2024年2月17日

许可协议

CSAPP hw3 上一篇

CSAPP hw8 下一篇