(9)int logicalNeg(int x);
①题目描述:
实现!运算符的功能
例子: logicalNeg(3) = 0, logicalNeg(0) = 1
允许的操作符: ~ & ^ | + << >>
最多操作符数目: 12
②大致思路:
可以通过取相反数进行非零判断。令y=~x+1(y=-x)并讨论x与y的符号位,有如下几种情况:
a. 当x为0时,两者符号位都为0。
b. 当x=0x8000 0000时,两者符号位都为1。
c. 当x既不为0也不为0x8000 0000时,两者符号位为01或10。
因此,可依真值表得
a n s = ( ∼ x ) & ( ∼ y ) ans=(\sim x)\&(\sim y)ans=(∼x)&(∼y)
③编程实现:
/* * logicalNeg - implement the ! operator, using all of * the legal operators except ! * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int logicalNeg(int x) { return ((~(~x + 1) & ~x) >> 31) & 1; }
(10)int howManyBits(int x);
①题目描述:
返回将X表示为补码所需的最小有效位数。
例子: howManyBits(12) = 5
howManyBits(298) = 10
howManyBits(-5) = 4
howManyBits(0) = 1
howManyBits(-1) = 1
howManyBits(0x80000000) = 32
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 90
②大致思路:
通过二分完成算法实现,具体设计如下:
我们举一个例子进行说明:x=0000 1000 1001 0000 0000 0000 0000 0000
a.令y=x>>16=0000 1000 1001 0000,shift16=(!!y)<<4使用(!!y)判断y是否为0,如果y为0,则返回0,说明前16位都为0,shift16=0,否则!!y=1,shift16=16,使x=x>>shift16=10001001 0000;
b.同理,令y=x>>8=0000 1000,shift8=(!!y)<<3使用(!!y) 判断y是否为0,如果y为0,则返回0,说明前8位都为0,shift8=0,否则!!y=1,shift8=8,使x=x>>shift8=00001000;
c.令y=x>>4=0000,shift4=(!!y)<<2使用(!!y) 判断y是否为0,如果y为0,则返回0,说明前4位都为0,shift4=0,否则!!y=1,shift4=4,使x=x>>shift4=00001000;
d.令y=x>>2=0000 10,shift2=(!!y)<<1使用(!!y) 判断y是否为0,如果y为0,则返回0,说明前2位都为0,shift2=0,否则!!y=1,shift2=2,使x=x>>shift2=000010;
e.令y=x>>1=0000 1,shift1=(!!y),使用(!!y) 判断y是否为0,如果y为0,则返回0,说明前1位都为0,shift1=0,否则!!y=1,shift1=1,使x=x>>shift1=00001;
f.最后对各个二分进行求和即可;
g.对于负数取反码即可,对于-1和0需要进行特殊考虑。
③编程实现:
/* howManyBits - return the minimum number of bits required to represent x in * two's complement * Examples: howManyBits(12) = 5 * howManyBits(298) = 10 * howManyBits(-5) = 4 * howManyBits(0) = 1 * howManyBits(-1) = 1 * howManyBits(0x80000000) = 32 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */ int howManyBits(int x) { int shift1, shift2, shift4, shift8, shift16; int sum; int t = ((!x) << 31) >> 31; int t2 = ((!~x) << 31) >> 31; int op = x ^((x >> 31)); shift16 = (!!(op >> 16)) << 4; op = op >> shift16; shift8 = (!!(op >> 8)) << 3; op = op >> shift8; shift4 = (!!(op >> 4)) << 2; op = op >> shift4; shift2 = (!!(op >> 2)) << 1; op = op >> shift2; shift1 = (!!(op >> 1)); op = op >> shift1; sum = 2 + shift16 + shift8 + shift4 + shift2 + shift1; return (t2 & 1) | ((~t2) & ((t & 1) | ((~t) & sum))); }
(11)unsigned float_twice(unsigned uf);
①题目描述:
以unsinged表示的浮点数二进制的二倍的二进制unsigned型
参数和结果都会被作为unsigned返回,但是会表示为二进制的单精度浮点值。
允许的操作符: 任何整数或者无符号数操作符包括: ||, &&. also if, while
最多操作符数目: 30
②大致思路:(exp表示阶码位、frac表示尾数位)
通过分析可知,共存在三种可能的情况,分别考虑如下:
a.当exp=0xff时,直接返回本身即可;
b.当exp=0时,分两种情况考虑:
当uf[22]=0时,然后将frac左移一位即可
当uf[22]=1时,将exp自增1,然后再将frac左移一位即可
c.对于其他情况,将exp自增1,然后再分两种情况:
当exp==0xff,令frac=0即可。
其余情况正常左移并返回即可
③编程实现:
/* * float_twice - Return bit-level equivalent of expression 2*f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * When argument is NaN, return argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_twice(unsigned uf) { unsigned int exp = 0x7f800000 & uf; unsigned int frac = 0x007fffff & uf; unsigned int s = 0x80000000 & uf; if (((~exp) & 0x7f800000) == 0) { return uf; } else { if (exp == 0) { if ((0x00400000 & uf) == 0) { frac = frac << 1; } else { exp = 0x00800000; frac = frac << 1; } } else { exp = exp + 0x00800000; if (((~exp) & 0x7f800000) == 0) frac = 0; } return (exp | frac | s); } }
(12)unsigned float_i2f(int x);
①题目描述:
返回int x的unsigned浮点数的二进制形式
参数和结果都会被作为unsigned返回,但是会表示为二进制的单精度浮点值
允许的操作符: 任何整数或者无符号数操作符包括: ||, &&. also if, while
最多操作符数目: 30
②大致思路:(exp表示阶码位、frac表示尾数位)
首先,我们可以知道int型数据的表示范围为-231~231-1。
通过分析可知,主要有三种情况:
a.用二进制下科学计数法表示int型数时,尾数位数<=23,例如0x00008001,此时将0x8001左移24-16=8位得到frac,而exp则为127+16-1;
b.当尾数位数>23时,找到位数最末一位记作x[i],然后对尾数的舍去分3种情况考虑,并初始化c=0:
当x[i-1]=1且x[i-2]、x[i-3]…x[0]都为0,且x[i]=1,令c=1;
当x[i-1]=1且x[i-2]、x[i-3]…x[0]不都为0,令c=1;
其余情况 令c=0;
c.特殊情况。
对于x为0或为0x8000 0000的情况,在处理前进行特判即可。
③编程实现:
/* * float_i2f - Return bit-level equivalent of expression (float) x * Result is returned as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point values. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_i2f(int x) { unsigned abs = x; unsigned s = 0x80000000 & x; unsigned tem = 0x40000000; unsigned exp_sign = 0; unsigned exp = 0; unsigned frac; unsigned c = 0; if (x == 0) return x; else if (x == 0x80000000) return (s + (158 << 23)); else { if (x < 0) abs = -x; while (1) { if (tem & abs) break; tem = tem >> 1; exp_sign = exp_sign + 1; } frac = (tem - 1) & abs; if (31 - 1 - exp_sign > 23) { int i = 30 - exp_sign - 23; if ((frac << (31 - (i - 1))) == 0x80000000) { if ((frac & (1 << i)) != 0) c = 1; } else if ((frac & (1 << (i - 1))) != 0) c = 1; frac = frac >> i; } else frac = frac << (23 - (31 - exp_sign - 1)); exp = 157 - exp_sign; return (s + (exp << 23) + frac + c); } }
(13)int float_f2i(unsigned uf);
①题目描述:
返回unsigned uf的整型数的二进制形式
参数和结果都会被作为unsigned返回,但是会表示为二进制的单精度浮点值
任何超过范围的数都应该返回 0x80000000u.
允许的操作符: 任何整数或者无符号数操作符包括: ||, &&. also if, while
最多操作符数目: 30
②大致思路:(exp表示阶码位、frac表示尾数位)
为了方便进行计算,可以将uf(unsigned float)切割成符号位s,阶码exp和位数frac,分情况讨论:
a.当exp=0或exp-127<0时,返回0;
b.当exp-127>=31时候,超出表示范围,于是返回0x80000000u;
c.当exp-127<=23,根据符号位返回值num>>(23-(exp-127))
③编程实现:
/* * float_f2i - Return bit-level equivalent of expression (int) f * for floating point argument f. * Argument is passed as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point value. * Anything out of range (including NaN and infinity) should return * 0x80000000u. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ int float_f2i(unsigned uf) { int exp = 0x7f800000 & uf; unsigned s = 0x80000000 & uf; int frac = 0x007fffff & uf; int frac2 = frac + 0x008fffff; int exp_sign = ((exp >> 23) - 127); if (exp == 0x7f800000) return 0x80000000u; else if (exp == 0) return 0; else if (exp_sign <= -1 && exp_sign >= -126) return 0; else if (exp == 31 && frac == 0 && s != 0) return 0x80000000; else if (exp_sign >= 31) return 0x80000000u; else if (exp_sign <= 23) frac2 = frac2 >> (23 - exp); else frac2 = frac2 << (exp - 23); if (s == 0) return frac2; else return -frac2; }
在Linux下测试以上函数是否正确,指令如下:
*编译:./dlc bits.c *测试:make btest ./btest
完成代码编写后进行编译测试:
运行程序并进行测试:
可以看到,代码全部正确。
五、实验总结与体会
位操作比高级语言难得多
相对于高级语言,通过使用移位取反等位操作对数值进行操作要比高级语言进行运算难的多。而且在运算过程中需要注意更多的细节。位运算也需要对底层逻辑更清楚更明确。在实验过程中,通过上网查阅资料了解不熟悉的细节,我最终顺利完成了实验。
数学技巧可以起到另辟蹊径的作用:
在本次实验中,例如第一题等,可以利用离散数学中的真值表技巧,列出真值表对函数进行求解,这也是一种好方法。
不能忽略特判:
对于后三个题中,需要特殊注意特判的情况,需要区别全0情况和全1情况进行分开讨论。对特殊值进行特判后不仅能提高代码的容错性,更能使程序逻辑更清晰。