《计算机整数编码实验》由会员分享，可在线阅读，更多相关《计算机整数编码实验（11页珍藏版）》请在金锄头文库上搜索。
1、计算机编码实验总体限制，只能使用！，单目运算符以及&,|,+,双目运算符， 禁止使用任何控制结构，禁止使用任何函数和宏，禁止使用任何形式 的类型转换。实验1:编写int bitAnd(int x, int y)函数只用或者丨实现x&y,并将结 果返回。实现方法：AND运算是两个为1,值为1，OR运算是有一个为1,值 就为1,因此,将两个数取反,然后再做或运算,最后再取反就可以 得到AND运算同样的效果。实验代码：int bitAnd(int x, int y)int ret;x = x;y = y;ret = x|y;ret = ret;return ret;实验2 编写函数int get B
2、y te(in t x, int n),取出x中的n号字节，并将 结果返回。编号从低位到高位，并且从0开始算起，使用操作符的数 量最多是6个。实现方法：每字节占用8Bits,因此要取n号字节只需要将数值右移 8*nBits,就可以，此外乘8操作相当于将n左移动3位。实验代码：int getByte(int x, int n)n = n n;return x&0xFF;实验3：编写函数int logicalShift(int x, int n)将x逻辑右移n位 (0=nn;return tmp;实验4：编写函数int bitCount(int x),统计x的二进制表示中1的数量， 并将结果返回。
3、要求不能使用if do while for switch等任何控制 结构，只能使用单目运算符：、双目运算符&、八、|、+、。 实现方法： 给定一个整数，统计其二进制数位中1的个数，例如 5 的二进制数 位中1的个数是 2。题目测试二进制数位的表示，假设整数为32位整型数，可以采 取分治算法来处理，问题可以变成32位整型数数位中包含1的数位 的个数，采用分治思想，变成高16位整型数数位中的包含1的数位 的个数和低16位整型数数位中包含1的数位的个数，然后再变成4 个8位整型数的数位中包含1的数位的个数，.,依次类推，变成1 位整型数中包含1的数位的个数。然后我们可以根据1位整型数中包 含1的数位
4、的个数，逆序得到32位整型数数据中包含1的个数。诚 然1位数包含1的数位的个数就是该1位数的数值，两个1位数相加 得到一个2位数包含1的数位的个数，依次向上，计算出32位数包 含的1的数位的个数。通过一个例子来验证上述说法，我们假设d是一个32位的整型数,其值是171H，其二进制表示是：101110001B,171H(1,0111,0001B)运算数位1171H(1,0111,0001B)d=171H数位2161H(1,0110,0001B)d=(d&0x55555555)+(d1)&0x55555555)数位4131H(1,0011,0001B)d=(d&0x33333333)+(d2)&0
5、x33333333)数位8104H(1,0000,0100B)d=(d&0xffffffff)+(d4)&Oxffffffff)数位165H(0101B)d=(d&0x00ff00ff) + (d8) &OxOOffOOff)数位325H(0101B)d=(d&0x0000ffff) + (d16) &OxOOOOffff)实验代码：将其转换成程序如下int bitCount(int x)unsigned int d = x;printf(%xn, d);d = (d&0x55555555)+(d1)&0x55555555);printf(%xn, d);d = (d&0x33333333)+
6、(d2)&0x33333333);printf(%xn, d);d = (d&0x0F0F0F0F)+(d4)&0x0F0F0F0F);printf(%xn, d);d = (d&0x00FF00FF)+(d8)&0x00FF00FF);printf(%xn, d);d = (d&0x0000FFFF)+(d16)&0x0000FFFF);printf(%xn, d);return d; 需要注意的是，针对移位操作对有符号数和无符号数的差别，对 有符号数来说，是将符号位插入到最左位，对于无符号来说， 是在最左位补零。实验5：编写函数int bang(int x)，不使用！实现！操作符，并将结果
7、返回， 只是用操作符号, &，；|,+,。要求只能使用操作符： ，&，八，|,+,，不能使用 if do while for switch 等任何控制 结构；并且操作符的使用数量限制为12个 实现方法： 所能使用的运算符中,能实现取反的只有,而是按位取反,可以通 过将给定整数的所有位1的数位进行汇总,汇总到最后一位上,之后 通过取反来得到结果。假定给定的整数是32位的，并假定它为x,通过x=x|(x16)运算先 将高16位汇总到低16位上；之后在通过x=x|(x8)，将为1的数 位汇总到低8位上，按照上述方法，最后将为1的数位汇总到Bit0 上。然后x&1就是需要的结果。代码表示如下:(x16
8、);x = x |(x8);x = x |(x4);x = x |(x2);x = x | (x1);return (x)&1;实验6：编写函数tmin(),返回补码表示的整型的最小值，并将结果返回，最 多使用4个操作符。实验原理：整数的最小值就是负数，负数的编码就是反码加1，因此 就32位数而言就是0x80000000。只保持符号位为1就可以。实验代码：int tmin(void) return 131;实验7：实现函数int fitsBits(int x, int n),如果x可以只用n位补码表 示则返回1,否则返回0 (1二n=32)。要求最多使用15个操作符。实验原理：一个数如果能左移
9、N位后，在右移N位，仍然等于这个数，表明 这个数可以用N位来表示。实验代码：int fitsBits(int x, int n)int s = 32-n;int m = x;m = ms;return !(mx);实验8：编写函数int divpwr2(int x, int n),计算x除以2的n次方的结 果，结果向零取整。要求最多使用15个操作符。实验原理：这道实验题，还是比较麻烦的，正数直接右移就行，但是负数右 移当不能整除时，是向无穷大靠近的；因此负数要加上进一个偏置， 然后再右移，结果才能正确；另外除以2的N次方能整除的条件是, 这个数的最低N位是0,负数要加上的偏置就是使最低N位变成
10、0， 并使第N +1位变成1。具体看实现中的代码以及注释。实验代码：int divpwr2(int x, int n)/获取符号位，用来区分正负数要不要加偏置/需要注意的是移位是算术移位如果x是负数，那么s全为1int s = x 31;/偏置数 低N位全部是位1unsigned int c = (1n;实验9：编写函数int negate(int x) 计算-x。实验原理：负数的表示反码加1实验代码：int negate(int x)return x+1;实验10：编写函数int isPositive(int x)，如果x大于0返回1，否则返回0，使用操作符的数量最大是8个。实现原理：大于0
11、的数，是非0正数，因此需要根据符号位确定是正数，还要不 是0。实验代码：int isPositive(int x)/确定符号位int s = x31;/判断是不是0int r = !(!x);/!s正数为1负数为0return !s&r;实验11：实现函数int isLessOrEqual(int x, int y),如果x小于等于y则 返回1，否则返回0。使用操作数的最大数量是24。实现原理：转化成两个问题，如果x, y符号相同，y-x的值是正数，如果x, y符号不同，那么x是负数。需要注意，符号相同相减不会发生溢出，符号不同时才有可能发 生溢出，因此单独依靠y-x的正负，不能得到x小于等于
12、y。 实验代码：int isLessOrEqual(int x, int y)/计算y-x并得到结果的符号位的值int rsl = y-x;int rs = rsl 31;/获取x, y的符号位int xs = x31;int ys = y31;/x, y的符号是否一样，不一样ds是1, 一样ds是0；int ds = xs八ys;/(ds&xs)符号不同单x是负数返回1/符号相同 但结果rs是正数(!ds&!rs)。返回1return (ds&xs)|(!ds&!rs)&1;实验12：编写函数in t ilog2(int x),求x以2为底的对数的结果(向下取整)。 返回结果,使用操作符的数
13、量最大位90个。实现原理：这是实验本质上是求最高位的1的位置,以32位整数为例,先看 最高位1是不是在高1 6位,可以利用! ! (x 1 6)表达式来计算,如 果！(x16)是1,表示在高16位，因此暂时将结果设置成c=16；之 后再逐次逼近，计算！(x(8+c)的值，如果结果仍然为1,那么就 将结果暂时设置成C二c+3；最后计算！(x(l+c)的结果，就能得到 最终的答案结果。实验代码：int ilog2(int x)int c = 0;c = (！(x16)4;c = c+(！(x(8+c)3);c = c+(！(x(4+c)2);c = c+(！(x(2+c)1);c = c+(！(x(1+c);return c;
