CSAPP3e 第二章作业

Posted on | Edited on | In | Comments:
My solution to Ch2's Hw

2.58

1
2
3
4
5
int isLittleEndian1()
{
	int a = 1;
	return ((char*)&a)[0];
}

2.59

1
2
3
4
int f2_59(int x, int y)
{
	return x&(((1<<(sizeof(int)-1)*8)-1)<<8)|(y&0xFF);
}

2.60

1
2
3
4
5
unsigned replaceByte(unsigned x, int i, unsigned char b)
{
	int t = ~0 - ((1LL<<(i+1<<3))-(1<<(i<<3)));
	return x&t|((unsigned)b<<(i<<3));
}

2.61

1
2
3
4
int A2_61(int x)
{
	return !(x^~0);
}
1
2
3
4
int B2_61(int x)
{
	return !x;
}
1
2
3
4
int C2_61(int x)
{
	return !((x&0xFF)^0xFF);
}
1
2
3
4
int D2_61(int x)
{
	return !((unsigned)x>>((sizeof(int)-1)<<3));
}

2.62

1
2
3
4
5
int isRightShiftAreArithmetic()
{
	int x = -1>>1;
	return x==-1;
}

2.63

1
2
3
4
5
unsigned srl(unsigned x, int k)
{
	unsigned xsra = (int)x>>k;
	return xsra&(1<<(sizeof(int)<<3)-k)-1;
}
1
2
3
4
5
6
int sra(int x, int k)
{
	int xsrl = (unsigned)x>>k;
	int t = ~0-(1<<k)+1 & x>>((sizeof(int)<<3)-1);
	return t|xsrl;
}

2.64

1
2
3
4
5
//题目中没有说bit从0开始计数还是从1开始，此处默认从0开始
int anyOddOne(unsigned x)
{
	return (x&0xaaaaaaaa)==0xaaaaaaaa;
}

2.65

1
2
3
4
5
6
7
8
9
10
int oddOnesV1(unsigned x)
{
	//思路，用xor消掉成对的1，不成对的记录下来
	x ^= x<<16;
	x ^= x<<8;
	x ^= x<<4;
	x ^= x<<2;
	x ^= x<<1;
	return x>>31;
}
1
2
3
4
5
6
7
8
9
10
int oddOnesV2(unsigned x)
{
	//思路与上一个函数类似
	x ^= x<<1;	//思考的时候只考虑奇数位，不需要考虑偶数位（从1开始计数bit位）
	x ^= x<<2;	//只考虑mod4==0的位置
	x ^= x<<4;	//只考虑mod8==0的位置
	x ^= x<<8;	//只考虑mod16==0的位置
	x ^= x<<16;	//只考虑mod32==0的位置
	return x>>31;
}

2.66

1
2
3
4
5
6
7
8
9
int leftMostOne(unsigned x)
{
	x |= x>>1;
	x |= x>>2;
	x |= x>>4;
	x |= x>>8;
	x |= x>>16;
	return x-(x>>1);
}

2.67

1
2
3
4
int intSizeIs32()
{
	return INT_MAX==0x80000000-1;
}

2.68

1
2
3
4
5
6
int lowerOneMark(int n)
{
	int t = -!(n-(sizeof(int)<<3));	//方法1
	return (1<<n)-1&~t | t;
//	return ((n!=(sizeof(int)<<3))<<n)-1;	//方法2
}

2.69

1
2
3
4
5
unsigned rotateLeft(unsigned x, int n)
{
	//移位sizeof*8不行，但是移位sizeof*8-1再移位1就可行了，上一题也可以这样搞
	return x>>((sizeof(unsigned)<<3)-n-1)>>1 | x<<n;
}

2.70

1
2
3
4
int fitBits(int x, int n)
{
	return x>>n-1==0 | x>>n-1==-1;
}

2.71

1
2
3
4
5
typedef unsigned pack_t;
int xbyte(pack_t word, int bytenum)
{
	return (int)word<<(3-bytenum<<3)>>24;
}

2.73

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int saturatingAdd(int x, int y)
{
	//方法一
	int t = (sizeof(int)<<3)-1;
	int p = ((unsigned)x>>t)+((unsigned)y>>t)+((unsigned)x+y>>t);
	t = ((unsigned)x>>t)+((unsigned)y>>t);
	return -(p==2&&t!=1)&INT_MIN | -(p==1&&t!=1)&INT_MAX | -(p==0||t==1)&x+y | -(p==3||t==1)&x+y;
  
	//方法二
	int t = (sizeof(int)<<3)-1;
	int p = ((unsigned)x>>t<<2)|((unsigned)y>>t<<1)|((unsigned)x+y>>t);
	return -(p==6)&INT_MIN | -(p==1)&INT_MAX | -(p!=1&&p!=6)&x+y;
  
	//方法三（from http://blog.csdn.net/yang_f_k/article/details/8857904）
	int w=sizeof(int)<<3;
	int sum = x+y;
	int mask = 1<<(w-1);
	int x_lmb = x&mask;
	int y_lmb = y&mask;
	int sum_lmb = sum&mask;
	
	int neg_of = x_lmb && y_lmb && (!sum_lmb);
	int pos_of = !x_lmb && !y_lmb && sum_lmb;
	
	(pos_of &&(sum=INT_MAX)) || (neg_of && (sum = INT_MIN)); //这一条不错
	return sum;
}

2.74

1
2
3
4
5
6
7
int tsubOk(int x, int y)
{
	int t = (sizeof(int)<<3)-1;
	int p = (unsigned)x>>t<<2 | (unsigned)-y>>t<<1 | (unsigned)x-y>>t;
	t = y==INT_MIN;
	return p!=6 && p!=1 && !t || t && p==6;
}

2.75

1
2
3
4
5
6
unsigned unsignedHightProd(unsigned x, unsigned y)
{
	unsigned t = signed_high_prod(x, y);
	int l = (sizeof(int)<<3)-1;
	return t + (x>>l)*x+(y>>l)*y;
}

2.76

1
2
3
4
5
6
7
8
9
10
11
void* Calloc(size_t nmemb, size_t size)
{
	size_t t = nmemb*size;
	void *p;
	if(!size || t/size==nmemb){
		p = malloc(t);
		if(!p)return NULL;
		memset(p, 0, t);
	}else return NULL;
	return p;
}

2.77

1
2
3
4
5
6
7
8
int f2_77(int x)
{
	int k1 = (x<<4)+x;
	int k2 = -(x<<3)+x;
	int k3 = (x<<6)-(x<<2);
	int k4 = -(x<<7)+(x<<4);
	return (k1==x*17)<<3 | (k2==x*-7)<<2 | (k3==x*60)<<1 | k4==x*-112;
}

2.78

1
2
3
4
5
6
int dividePower2(int x, int k)
{
	int l = sizeof(int)<<3;
	l = -(x>>l-1);
	return (l<<k)-l+x >> k;
}

2.79

1
2
3
4
5
6
7
int mul3div4(int x)
{
	x = (x<<2) - x;
	int l = sizeof(int)<<3;
	int t = -(x>>l-1);
	return (t<<2)-t+x >> 2;
}

2.80

1
2
3
4
5
6
7
8
9
10
int threefourths(int x)
{
	int t = x&0x3;
	int t2 = -(x>>(sizeof(int)<<3)-1);
	int p = (x>>2);
	p = (p<<1)+p;
	t = (t<<1)+t;
	p += (t>>2) + (t2&&t);
	return p;
}

2.81

1
2
3
4
5
6
7
8
9
10
int hw281A(int k)
{
	return 0-(1<<k-!!k<<!!k);	//k may equal to 0 or 32;
}

int hw281B(int j, int k)
{
	int t = k+j;
	return (0-(1<<j-!!j<<!!j)) ^ (0-(1<<t-!!t<<!!t));
}

2.82

1
2
3
4
5
6
7
8
/*
 * A: NO; x== 0x10000000, B==rand();
 * B: Yes; 
 * C: Yes; 因为，取反操作之后立刻截断与计算完之后再截断是等价的。
 * 可以两边都加上1，从而左右两个过程（截断之前）都是两个负数相加
 * D: Yes;
 * E: Yes;
 */

2.83

$\sum_{i=1}^{\infty}Y2^{-ki}$

2.84

1
return ((sx<sy) && ux!=0 && uy!=0x80000000) | (sx==sy) & !!(ux-uy);