GZU 深入了解计算机系统基础OJ答案记录第二章 平时作业

题目1：​ilog2函数

描述：定义ilog2函数 - 返回 floor(log base 2 of x), x > 0 （即求以2为底x的对数，且向下取整） 函数原型为：int ilog2(int x)； 例如：ilog2(17) = 4 main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",ilog2(x));

    return 0;

}
解决思路：刚好可以使用二进制的移位操作代替除2，统计次数就可以得到ilog2的值

代码实现：

ilog2(int x){
    int i=0;
    while(x>=2){
        x=x>>1;
        i++;
    }
    return i;
}

题目2：isLessOrEqual函数

描述： 设计一个isLessOrEqual函数，在不使用任何关系运算符的情况下，判断x <= y是否成立，成立则返回1，否则返回0

函数原型为：int isLessOrEqual(int x, int y)；

例如：isLessOrEqual(4, 5) = 1

main函数已经写好，请根据main函数的内容完成该函数的设计：

int main(){

    int x,y;

    scanf("%d%d",&x,&y);

    printf("%d\n",isLessOrEqual(x,y));

    return 0;

} 

解决思路：相减移位取符号位来判断是正数还是负数 tip:因为int占4个字节32位，取符号位右移31，并且由于这里是有符号数,>>在这里是算术右移，而非逻辑右移（无符号数>>是逻辑右移），负数得到的是0xFFFF,也就是负1；

代码实现：

isLessOrEqual(int x,int y){
  
    return (x-y)>>31==-1?1:0;
}

题目3：isPositive函数

描述：定义一个函数，在不使用任何关系运算符的情况下，对参数x的符号进行判断，如果大于0则返回1，否则返回1 函数原型为：int isPositive(int x)； 例如：isPositive(-1) = 0 main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",isPositive(x));

    return 0;

}

解决思路：和上一题类似，只不过0也是正数，我们把0-1就行了，因为返回的是-1，和0，把移位操作结果+1就行

代码实现：

isPositive(int x){
	return (((x-1)>>31)+1);
}

题目4：bitAnd函数

描述：设计一个bitAnd函数，在不使用按位与运算符&的情况下，实现按位与运算，可以使用按位取反~和按位或| 函数原型为：int bitAnd(int x, int y)；

例如：bitAnd(6, 5) = 4

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x,y;

    scanf("%d%d",&x,&y);

    printf("%d\n",bitAnd(x,y));

    return 0;

}

思路：可以看一下p35 图2-7的|运算，对照着看，x和y同时取反再|刚好得到x|y的反，然后取反就可以了

实现代码：

bitAnd(int x,int y){
	return ~(~x|~y);
}

题目5：negate函数

设计一个函数，在不使用负号的情况下，返回-x

函数原型为：int negate(int x)；

例如：negate(1) = -1

main函数已经写好了，请根据main函数的内容完成该类的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",negate(x));

    return 0;

}

思路：由于是有符号数，比如0[0x00]取反得到的是全1[0xffff],也就是-1，+1就可以了

实现：（这里需要加上主函数提交，是oj的问题）

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",negate(x));

    return 0;

}
negate(int x){
	return ~x+1;
}

题目6：bang函数

定义一个函数，在不使用逻辑非运算符!的情况下，用于求!x

函数原型为：int bang(int x)；

例如：bang(5) = 0, bang(0) = 1

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",bang(x));

    return 0;

}

思路：负数 = 负数的绝对值按位取反+1 负数按位取反+1 =负数的绝对值 由于是逻辑运算,我们只需要得到0或者1就行，使用&&得到，然后位取反~

+2 是因为&&得到的是有符号数的0x00或者0x01,按位~得到的只是-1和0，+1之后才能得到0和1，然后负数还需要+1，所以这里+2是+1+1

实现代码：

bang(int x ){
	return ~(x&&x)+2;
}

题目7：divpwr2函数

定义divpwr2函数，在不使用除法运算符的情况下，计算 x/(2^n)，0 <= n <= 30，要求向 0 舍入

例如：divpwr2(15, 1) = 7, divpwr2(-33, 4) = -2

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x,n;

    scanf("%d%d",&x,&n);

    printf("%d\n",divpwr2(x,n));

    return 0;

}

思路：因为除数是2，刚开始想直接>>n的,但是发现由于是有符号数，负数不能这样，比如-1不管>>n,n是多少，结果都是-1，也就是算术右移左边补一造成的，所以把负数换成正数(~x+1)，再把得到的结果换成负数就行了(~1)((~x+1)>>n)+1{不要管这里加的（~1）格式问题，看代码就行，或者不要这个1}，原本是正数的不管x>>n

代码实现：

divpwr2(int x,int n){
	return x>=0?x>>n:~((~x+1)>>n)+1; 
}

题目8：showIP函数

设计一个函数，该函数将给定的任意整型数据视为一个IPv4地址，并以点分十进制形式显示该IP地址。

例如：整数为-1455049865（十六进制表示为0xA945B377），对应的IP地址为：169.69.179.119。

函数原型为：void showIP(int x)；

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    showIP(x);

    return 0;

}

思路：刚开始是想使用掩码按位取对应的位数就行，后面发现取出来的十进制结果不对，忘了对应移位操作去权了

代码:

void showIP(int x){
	printf("%d.",(x&0xff000000)>>24);
	printf("%d.",(x&0x00ff0000)>>16);
	printf("%d.",(x&0x0000ff00)>>8);
	printf("%d",x&0x000000ff);
}

题目9：fitsBits函数

设计一个函数，用于测试参数x是否能被n位补码整数表示（1 <= n <= 32）。如果能返回1，否则返回0

函数原型为：int fitsBits(int x, int n)；

例如： fitsBits(5, 3) = 0, fitsBits(-4, 3) = 1

main函数已经写好了，请根据main函数内容完成该函数的设计：

int main(){

    int x,n;

    scanf("%d%d",&x,&n);

    printf("%d\n",fitsBits(x,n));

    return 0;

}

思路：题目意思就是判断n位能否表示有符号的x

只要判断x是不是比B2Tn(max)大就行，相当于n位表示的对半砍减一

这里分正数负数，负数按位取反换成正数判断,说一下这里的>>n-2 >>1 就已经相当于除2，然后还要取一半减一，所以要-2

代码：

fitsBits(int x,int n){
	return x>=0?!((x>>(n-2))-1):!((~x>>(n-2))-1);
}

题目10：umax函数

设计一个函数，返回长度为n位（1<=n<=32）的无符号整数能表示的最大值。

函数原型为：unsigned umax(int n)；

例如： umax(3)=7，umax(6)=63；

main函数已经写好了，请根据main函数内容完成该函数的设计：

int main(){

    int n;

    scanf("%d",&n);

    printf("%u\n",umax(n));

    return 0;

}

思路：想直接1<<n 移位操作解决的，但是n=32会溢出，所以换成一半加一半-1

实现：

umax(int n){
	return 2*(1<<(n-1))-1;
}

题目11：tmax函数 设计一个函数，返回长度为n位（2<=n<=32）的有符号整数能表示的最大正数。

函数原型为：int tmax(int n)；

例如： tmax(3)=3，tmax(6)=31；

main函数已经写好了，请根据main函数内容完成该函数的设计：

int main(){

int n;

scanf("%d",&n);

printf("%d\n",tmax(n));

return 0;

} 思路：懒得写直接改上一个一半

tmax(int n){
	return 2*(1<<(n-2))-1;
}

题目12：tmin函数

设计一个函数，返回长度为n位（1<=n<=32）的有符号整数能表示的最小负数。

函数原型为：int tmin(int n)；

例如： tmin(3)=-4，tmin(6)=-32；

main函数已经写好了，请根据main函数内容完成该函数的设计：

int main(){

    int n;

    scanf("%d",&n);

    printf("%d\n",tmin(n));

    return 0;

}

思路：直接上一个按位取反~

tmin(int n){
	return ~(2*(1<<(n-2))-1);
}

题目13：twosComplement函数

设计一个函数，用于输出一个整型数据的32位二进制补码编码。

函数原型为：void twosComplement(int x);

例如：twosComplement(-1)的输出为：11111111111111111111111111111111

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    twosComplement(x);

    return 0;

}

思路：网上的做法大多是短除法，这里的方法是自己想的，利用逻辑右移和掩码来取位权，主要工作在如何把算术右移转为逻辑右移

代码：

#include <stdio.h>
int main(){
    int x;
	scanf("%d",&x);
    twosComplement(x);
    return 0;

}
void twosComplement(int x){
	int i=32;
	int w=0x80000000;
	printf("%d",(~(x&w)>>i-1)+1);
	i--;
	w=-(w>>1);
	while(i>0){
		printf("%d",(x&w)>>i-1);
		i--;
		w=w>>1;
	}
}

题目14：binMirror函数

设计一个函数，该函数返回一个整数数据的二进制镜像数。所谓二进制镜像数，是指二进制表示和该数的二进制表示正好逆序的数。

例如：二进制序列1010的逆序列是0101

函数原型为：int binMirror(int x)；

例如：binMirror(1)=-2147483648

main函数已经写好了，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",binMirror(x));

    return 0;

} 

思路：他这里我理解的是最高位和最低为依次对调换位，我这里的思路利用掩码0x00000001,0x80000000直接取每一位上的位权然后再用移位操作来实现换位，最后全部相加就得到换位之后的值了；不过还有一点疑惑的，我寻思-1不是全是1吗？0xffffffff,那它的镜像应该是他自己吗？但是我的结果是-131072，我感觉我代码是有问题的，但是oj上过了。。。。无语

代码：

binMirror(int x){
	int count=0;
	int i,j;
	int w=0x00000001;
	int n=0x80000000;
	for(i=0,j=31;i<j;i++,j--){	
		count+=((~(x&n)>>j-i)+1)+(x&w)<<j-i;
		w=w<<1;
		n=n>>1;
	}
	return count;
}

题目15：bitCount函数

设计一个函数，用于返回一个整型数据中1的个数。

函数原型为：int bitCount(int x)；

例如：bitCount(5) = 2, bitCount(7) = 3

main函数已经写好，请根据main函数的内容完成该函数的设计：

int main(){

    int x;

    scanf("%d",&x);

    printf("%d\n",bitCount(x));

    return 0;

} 

思路：移位取位权为1，统计，搞定

代码：

bitCount(int x){
	int count = 0;
	int n=0x00000001;
	int i;
	for(i=0;i<32;i++){
		if((x&n)>>i==1){
			count+=1;
		}
		n=n<<1;
	}
	return count=x<0?count+1:count;
	
}

题目16：logicalShift函数

对有符号整型数据使用>>右移运算符进行操作进行的是算术右移。现在请设计一个函数，要求对有符号整型数据进行逻辑右移。

该函数的原型是：int logicalShift(int x, int n)；(0<=n<=31)

例如：logicalShift(0x87654321,4) 的结果应该为 0x08765432

main函数已经写好了，请根据main函数的情况完成该函数的设计：

int main(){

    int x,n;

    scanf("%x%d",&x,&n);

    printf("%x\n",logicalShift(x,n));


    return 0;

}

思路：我们之前实现的只是逻辑右移的取位权，这里需要的是直接逻辑右移，判断正负数，负数去最高位位权，然后正常处理就行

实现：

logicalShift(int x,int n){	
	return x<0?((x>>1)-0x80000000)>>n-1:x>>n;;
}

题目17：getByte函数

设计一个函数：int getByte(int x, int n)；

该函数将参数x的值的第n个字节取出（0 <= n <= 3）并返回

例如：getByte(0x12345678,1) = 0x56

main函数已经写好，请根据main函数的内容，完成该函数的设计：

int main(){

	int x,n;

	scanf("%x%d",&x,&n);  //注意，x以16进制格式输入 

	printf("%x\n",getByte(x,n)); //结果以16机制格式输出 

	return 0;

}

思路：掩码移位取对应字节，再移位就行，一字节=8位

实现：

getByte(int x,int n){
	return (x&0x000000ff<<n*8)>>n*8;
}

题目18：clearMask函数

设计一个函数：int clearMask(int x, int n)；

该函数将参数x的值的第n位设置为0（0 <= n <= 31）并返回新的值

例如：clearMask(7, 5) = 7

main函数已经写好，请根据main函数的内容，完成该函数的设计：

int main(){

	int x,n;

	scanf("%d%d",&x,&n);

	printf("%d\n",clearMask(x,n));

	return 0;

}

思路：原本想用0xfffffffe来移位的，但是右边补的是0，然后用f代替e减一就可以了

函数：

clearMask(int x,int n){
	int w=0xffffffff;
	return x&((w<<n)-1);
}

题目19：setMask函数

设计一个函数：int setMask(int x, int n)；

该函数将参数x的值的第n位设置为1（0 <= n <= 31）并返回新的值

例如：setMask(7, 5) = 39

main函数已经写好，请根据main函数的内容，完成该函数的设计：

int main(){

    int x,n;

    scanf("%d%d",&x,&n);

    printf("%d\n",setMask(x,n));

    return 0;

}

思路：这个和上一个差不多，只不过是把0换成1，注意用|就行

代码：

setMask(int x,int n){
	int w=0x00000001;
	return x|(w<<n);
}