コンピュータシステムの作業を深く理解する1 2.61 2.65 2.73 2.76解答

2.61
A !(~x)
B !x
C !(~ (x | 0x00ffffff))
D !(~ (x | 0xffffff00))
2.65
分析:本題は12回の操作に制限されているため、ビットごとにそのビットが1であるかどうかを計算することはできません.本題を考えると1の個数のパリティを判断するだけで,合計何個1があるかを計算する必要はない.では,偶数個1を除去できれば結果に影響を及ぼさないことを考慮し,偶数個1を迅速に除去する必要がある.異或演算はちょうど同じ1の時を0にすることができるからだ.次いで、分治法を用いて、全体的な異和を用いて操作回数を減少させる.
操作:1
1.上位16位と下位16位が一致した場合、元の32位のパリティは、現在の上位16位と一致する.
2.同理上位8位と下位8位が一致するか.
3.同理上位4位と下位4位が一致するか.
4.同理前2位と後2位が一致するか.
5.同理上位1位と下位1位が一致するか.
最後は最後の方が1なのか0なのかを判断するだけです.
 

int even_ones(unsigned x)

{

	unsigned  y = x >> 16; x ^= y;

	y = x >> 8; x ^= y;

	y = x >> 4; x ^= y;

	y = x >> 2; x ^= y; 

	y = x >> 1; x ^= y; 



	return !(x & 1);

	

}

 
2.73
【解析】まずオーバーフローの有無を判断し、判断記号(<,>)を用いることができないため、記号ビットを考慮することができ、(x+y)の記号ビットとxとyの記号ビットが異なるとオーバーフローが発生する.これは2回の異和と1回の操作で完了することができる.
命令ans=x+y
ALL=(x^ans)&(y^ans)>>(intBitCnt-1);明らかに算術オーバーフローの場合、ALLの32ビットの値はいずれも1(111.....111)であり、そうでなければALL=0であり、Ps:算術右シフトであるためである.
そして正オーバーフローか負オーバーフローかを判断し続け,xまたはyのシンボルビットを見るだけで判断できる.
令x_sign= x >> (intBitCnt – 1); オーバーフローしている場合x_sign=0でない場合、各ビットの値は1(111....111)です.
返された結果については、ans|ALL以降、オーバーフローした場合は結果が全1となり、そうでなければ結果はx+yとなる.オーバーフローしている場合は減算(1<<(intBitCnt–1))するだけで、負のオーバーフローで減算(1<(intBitCnt-1)^111...111(すべて1)でよい場合、0を減算しません.
このように,上記の演算に関与する1がオーバーフローするかどうか,正負のオーバーフローが関係しているかどうかであればよい.
ALL&1=1はオーバーフローの判定条件です.
x_sign& ALL = 111.....111(全1)は負のオーバーフローの条件であり、0は正のオーバーフローであり、オーバーフローしない可能性がある.

int saturating_add(int x,int y)

{

	int intBitCnt = sizeof(int) << 3;

	int ans = x + y;

	int ALL = (( x ^ ans) & (y ^ ans)) >> ( intBitCnt - 1);

	int x_sign = x >> ( intBitCnt  - 1);

	return (ans | ALL) - ( (ALL & 1) << ( intBitCnt - 1))^ (x_sign & ALL);

}

2.76
AK = 5 【code】x<<2+x
Bk = 9 【code】x<<3+x
Ck = 30【code】x<<5-x<<1
Dk = -56 【code】x<<3- x << 6