首页 > > 程序设计 > C/C++ >

CSAPP: 位操作实现基本运算

2019-10-28 06:19:08来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

CSAPP: 位操作实现基本运算

目录

  • 实验要求
  • 实现代码
    • 1、pow2plus1
    • 2、pow2plus4
    • 3、bitXor
    • 4、tmin
    • 5、isTmax
    • 6、allOddBits
    • 7、negate
    • 8、isAsciiDigit
    • 9、conditional
    • 10、isLessOrEqual
    • 11、logicalNeg
    • 12、howManyBits
    • 13、floatScale2
    • 14、floatFloat2Int
    • 15、floatPower2

@(位操作实现简单函数)

实验要求

给出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作为底数
}

原文链接:https://www.cnblogs.com/ustca/p/11740382.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：测试博客

下一篇：cin.get()解密

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签