CSAPP: 位操作实现基本运算
程序员文章站
2022-04-15 14:42:15
@ "TOC" 实验要求 给出15个函数,规定了实现每个函数需要的逻辑和算术操作符(规定数量)。 只能使用规定的操作符! ˜ & ˆ | + 不能使用循环或者条件语句 不能使用超过8位的常数(ff) 实现代码 1、pow2plus1 7、negate 8、isAsciiDigit 9、conditi ......
目录
@(位操作实现简单函数)
实验要求
给出15个函数,规定了实现每个函数需要的逻辑和算术操作符(规定数量)。
只能使用规定的操作符! ˜ & ˆ | + << >>
不能使用循环或者条件语句
不能使用超过8位的常数(ff)
实现代码
1、pow2plus1
/* * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 */ int pow2plus1(int x) { /* exploit ability of shifts to compute powers of 2 */ return (1 << x) + 1; }
2、pow2plus4
/* * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 */ int pow2plus4(int x) { /* exploit ability of shifts to compute powers of 2 */ int result = (1 << x); result += 4; return result; }
3、bitxor
/* bitxor - x^y using only ~ and & * example: bitxor(4, 5) = 1 * legal ops: ~ & * max ops: 14 * rating: 1 */ int bitxor(int x, int y) { return (~(x&y))&(~(~x&~y));//列出真值表 }
4、tmin
/* tmin - return minimum two's complement integer * legal ops: ! ~ & ^ | + << >> * max ops: 4 * rating: 1 */ int tmin(void) { return 1<<31;//0x80000000 }
5、istmax
/* istmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * legal ops: ! ~ & ^ | + * max ops: 10 * rating: 1 */ int istmax(int x) { return !(x+x+2) & !!(~x);//x+1+x+1溢出并且非全一 //x: 0111 1111 1111 1111 1111 1111 1111 1111 //x+1: 1000 0000 0000 0000 0000 0000 0000 0000 //x+1+x: 1111 1111 1111 1111 1111 1111 1111 1111 //x+1+x+1:0000 0000 0000 0000 0000 0000 0000 0000 }
6、alloddbits
/* alloddbits - return 1 if all odd-numbered bits in word set to 1 * where bits are numbered from 0 (least significant) to 31 (most significant) * examples alloddbits(0xfffffffd) = 0, alloddbits(0xaaaaaaaa) = 1 * legal ops: ! ~ & ^ | + << >> * max ops: 12 * rating: 2 */ int alloddbits(int x) { x = (x>>16) & x; x = (x>>8) & x; x = (x>>4) & x; x = (x>>2) & x; return (x>>1)&1; // &运算符的“归一性” //1010 1010 1010 1010 1010 1010 1010 1010 //0000 0000 0000 0000 1010 1010 1010 1010 //0000 0000 0000 0000 0000 0000 1010 1010 //0000 0000 0000 0000 0000 0000 0000 1010 //0000 0000 0000 0000 0000 0000 0000 0010 // 可以反推理解:后四位四次翻转得第一行 // 只要倒数第二位为1成立,反推后所有的奇数位都为1 }
7、negate
/* negate - return -x * example: negate(1) = -1. * legal ops: ! ~ & ^ | + << >> * max ops: 5 * rating: 2 */ int negate(int x) { return ~x+1; //带符号位取反加一即为相反数 }
8、isasciidigit
/* isasciidigit - return 1 if 0x30 <= x <= 0x39 (ascii codes for characters '0' to '9') * example: isasciidigit(0x35) = 1. * isasciidigit(0x3a) = 0. * isasciidigit(0x05) = 0. * legal ops: ! ~ & ^ | + << >> * max ops: 15 * rating: 3 */ int isasciidigit(int x) { // 0x30 = 0011 0000b 0x39 = 0011 1001b int a = (x>>4) ^ 0x3; // 判断5、6位是否全1 int b0 = (x>>3) & 1; // 判断第4位是否为1 int b1 = (x>>2) ^ 1; // 判断第3位是否为1 int b2 = (x>>1) ^ 1; // 判断第2位是否为1 return (!a) & ((!b0) | (b0&b1&b2)); // 如果5、6位全1 且 (4位为0或4位为1,2、3位为0) }
9、conditional
/* conditional - same as x ? y : z * example: conditional(2,4,5) = 4 * legal ops: ! ~ & ^ | + << >> * max ops: 16 * rating: 3 */ int conditional(int x, int y, int z) { x = !x; // 将x设置为0或1 x = (x<<31)>>31; // 将x的0或1拓展到32位全0或全1 return (~x&y) | (x&z); // x为真则~x全1返回y,为假则x全1返回z }
10、islessorequal
/* islessorequal - if x <= y then return 1, else return 0 * example: islessorequal(4,5) = 1. * legal ops: ! ~ & ^ | + << >> * max ops: 24 * rating: 3 */ int islessorequal(int x, int y) { int z,s,sx,sy; sx = (x>>31)&1; // 取x的符号位 sy = (y>>31)&1; // 取y的符号位 z = x + ~y + 1; // z = x-y s = ((z>>31) & 1) | (!(z^0)); // 取z的符号位,s为真时x<y或者z全0(x==y) return ((!(sx^sy))&s) | (sx&(!sy)); // xy同号且z<=0 或 x<=0 y>=0 }
11、logicalneg
/* 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) { // |运算符的“分裂性” x |= x>>16; // 若高16位有1,则传递给低16位的对应位 x |= x>>8; // 若低16位的高8位有1,则传递给低8位的对应位 x |= x>>4; // 若低8位的高4位有1,则传递给低4位的对应位 x |= x>>2; // 若低4位的高2位有1,则传递给低2位的对应位 x |= x>>1; // 若低2位的高1位有1,则传递给最低1位 x ^= 1; // 只要x包含1,则必定会导致此时的x为1,x^=1即取反 return x&1; }
12、howmanybits
/* 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 s,c1,c2,c3,c4,c5,c6; int cnt = 0; // 计数 s = (x>>31)&1; // 符号位 x = ((s<<31)>>31) ^ x; // 取反x s = !!(x>>16); // 判断高16位是否有1,有则s为1 c1 = s<<4; // 若高16位有1,则低16位可以计数16 x >>= c1; // 右移将已经计数的位移除,c1若为0,则用折半的长度判断 s = !!(x>>8); // 用8位的长度去判断,有效位的个数计入c2 c2 = s<<3; x >>= c2; s = !!(x>>4); // 用4位的长度去判断,有效位的个数计入c3 c3 = s<<2; x >>= c3; s = !!(x>>2); // 用2位的长度去判断,有效位的个数计入c4 c4 = s<<1; x >>= c4; s = !!(x>>1); // 用1位的长度去判断,有效位的个数计入c5 c5 = s; x >>= c5; c6 = !!x; // 判断最低位是否为1 cnt = c1+c2+c3+c4+c5+c6+1; // 将每次获得的低位有效位相加,再加1位符号位 return cnt; }
13、floatscale2
/* floatscale2 - 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 floatscale2(unsigned uf) { unsigned f = uf; if ((f & 0x7f800000) == 0)// 如果阶码为0 f = ((f & 0x007fffff) << 1) | (0x80000000 & f); // 尾数不为0则尾数左移1位,尾数第1位为1则阶码加1,尾数为0则uf为0返回0 else if ((f & 0x7f800000) != 0x7f800000)// 如果阶码不为0,且非全1 f = f + 0x00800000;// 阶码加1 return f; }
14、floatfloat2int
/* floatfloat2int - 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 floatfloat2int(unsigned uf) { unsigned inf = 1<<31; // inf = maxint+1 int e = (uf>>23) & 0xff;// 阶码 int s = (uf>>31) & 1; // 符号位 if (uf == 0) return 0; uf <<= 8; // 左移保留至阶码最后1位 uf |= 1<<31; // 阶码最后一位设为1 uf >>= 8; // 高八位全0 e -= 127; // 阶数 if ((uf & 0x7f80000) == 0x7f80000 || e >= 32) return inf; // 超过int范围返回inf if (e < 0) // 小数返回0 return 0; if (e <= 22) // 位数小于等于22位,尾数位右移 uf >>= 23-e; else uf <<= e-23; // 尾数大于22位,尾数为左移 if (s) uf = ~uf + 1;// 若原uf为负数,则对此处的正数uf取反加1得其相反数 return uf; }
15、floatpower2
/* floatpower2 - return bit-level equivalent of the expression 2.0^x * (2.0 raised to the power x) for any 32-bit integer x. * * the unsigned value that is returned should have the identical bit * representation as the single-precision floating-point number 2.0^x. * if the result is too small to be represented as a denorm, return * 0. if too large, return +inf. * * legal ops: any integer/unsigned operations incl. ||, &&. also if, while * max ops: 30 * rating: 4 */ unsigned floatpower2(int x) { unsigned inf = 0xff << 23; // 阶码全1 int e = 127 + x; // 得到阶码 if (x < 0) // 阶数小于0直接返回0 return 0; if (e >= 255) // 阶码>=255直接返回inf return inf; return e << 23; // 直接将阶码左移23位,尾数全0,规格化时尾数隐藏有1个1作为底数 }
上一篇: 设计模式-工厂模式
下一篇: MySQL的sleep函数的特殊特现象