• scau CSAPP datalab1

    1.用~和&运算实现异或(^)操作

    //* 
     * bitXor - x^y using only ~ and & 
     *   Example: bitXor(4, 5) = 1
     *   Legal ops: ~ &
     *   Max ops: 14
     *   Rating: 1
     */

    可以参考一下德·摩根律

     

    1. int bitXor(int x, int y) {
    2.   return ~(~x&~y)&~(x&y);
    3. }

    2.求二进制补码最小值

    /* 
     * tmin - return minimum two's complement integer 
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 4
     *   Rating: 1
     */ 

    1. int tmin(void) {
    2.  
    3.   return 1<<31;
    4.  
    5. }

    3.判断一个数是否为补码表示的最大值

    /*
     * isTmax - returns 1 if x is the maximum, two's complement number,
     *     and 0 otherwise 
     *   Legal ops: ! ~ & ^ | +
     *   Max ops: 10
     *   Rating: 1
     */ 

    方法一：

    补码表示的最大值为：0x 7fff ffff，其用二进制表示就是0111 1111 .... 1111

    我们发现，当0x 7fff ffff加1就变成了tmin，也就是1000 0000 .... 0000

    那么，把tmin减1就可以得到这个补码表示的最大值了，由于不能用减号，我们可以加-1，而-1可以写成~0x1+1

    1. int isTmax(int x) {
    2.   int ans=0x1<<31;
    3.   int max=ans+(~0x1+1);
    4.   return !(max-x);
    5. }

    方法二：

    以四位为例，则最大值为x=0111，我们将x+1后再取反，又得到了x。

    不信你看，x+1=1000，~(x+1)=0111，因此我们用异或操作来判断它是不是最大值->~(x+1)^x。

    不过，这种方法有个特例。当x=-1时，也就是x=1111，x+1=0000（发生了溢出），~(x+1)=1111，

    ~(x+1)^x =1111，所以要加一个判断条件，判断它是不是-1

    1. int isTmax(int x) {
    2.   return !(~(x+1)&x) && !!(x+1);
    3. }

    4.判断是否所有的奇数位的数字都为1

    /* 
     * 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
     */

    构造所有奇数位为1的数——0x AAAA AAAA（也就是1010 1010 1010 .... 1010），注意，最右边的一位是第0位哦~

    然后我们将x与0x AAAA AAAA做&运算，这可以只保留x的奇数位，再判断其与0x AAAA AAAA是否相等即可，若相等则得0，!0=1；若不相等则得1，!1=0

    1. int allOddBits(int x) {
    2.   int a=0xAA<<8;
    3.   int b=0xAA<<16;
    4.   int c=0xAA<<24;
    5.   int d=a|b|c;
    6.   return !((x&d)^d);
    7. }

    5.不用"-"，求-x

    /* 
     * negate - return -x 
     *   Example: negate(1) = -1.
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 5
     *   Rating: 2
     */

    x+(-x)=0，而x+(~x)=-1，可得（-x）= (~x)+1 

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

    6.计算输入值是否为0-9的ASCII值

    /* 
     * 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
     */

     

    其实我觉得吧，不会做题主要是没有耐心看题目，现在重新回头看看这些题，倒也没有想象中的那么难了。

    这道题其实就是让我们判断输入值是否在[0x30，0x39]之间

    0x30的位级表示为0011 0000，0x39的位级表示为0011 1001

    对于输入值x，我们要先满足x<<4==3，也就是得到x的前四位，前四位要等于3，然后后四位在0-9之间就好了。

    首先，我们可以用x & 0xF来保留x的后四位（&运算——与1相与是本身，与0相与是0）

    7.使用位级运算实现C语言中的 x?y:z三目运算符

    /* 
     * conditional - same as x ? y : z 
     *   Example: conditional(2,4,5) = 4
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 16
     *   Rating: 3
     */

    好的，什么是三目运算符呢？我来简单说一下。

    就是可以把它看成一个if-else语句,如果满足条件x，则执行y，否则执行z

    这道题就可以看成if(x!=0) return y;  else return z;

    1. int conditional(int x, int y, int z) {
    2.   x = !!x;
    3.   x = ~x+1;
    4.   return (x&y)|(~x&z);
    5. }

    我们需要寻找一种方法，当x!=0的时候让x变成0x FFFF FFFF

    1取反后加1就是0x FFFF FFFF了，那么怎样得到1呢？就用两个非运算就可以了。当x!=0时，第一次非运算得到0，再进行一次非运算就可以得到1了。

    若x!=0，则x经过一系列运算变成了0x FFFF FFFF，再和y进行与运算就可以保留y的值了；把x取反，变成了0x 0000 0000，与z进行与运算还是0

    若x==0，则x经过一系列运算变成了0x 0000 0000，与y进行与运算变成0；取反后成为0x FFFF FFFF，和z进行与运算得z的值

    完蛋，这道题把我也绕晕了 

    希望有朋友可以教教我TUT

    8.使用位级运算实现<=；如果x<=y，则返回1；否则返回0

    /* 
     * isLessOrEqual - if x <= y  then return 1, else return 0 
     *   Example: isLessOrEqual(4,5) = 1.
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 24
     *   Rating: 3
     */

    判断x<=y有两种方法，一个是x和y的符号相同，且y-x>=0；一个是x和y的符号不同，但x<0

    1. int isLessOrEqual(int x, int y) {
    2.   int negX=~x+1;//-x
    3.   int addX=negX+y;//y-x
    4.   int checkSign = addX>>31&1; //y-x的符号
    5.   int leftBit = 1<<31;//最大位为1的32位有符号数
    6.   int xLeft = x&leftBit;//x的符号
    7.   int yLeft = y&leftBit;//y的符号
    8.   int bitXor = xLeft ^ yLeft;//x和y符号相同标志位，相同为0不同为1
    9.   bitXor = (bitXor>>31)&1;//符号相同标志位格式化为0或1
    10.   return ((!bitXor)&(!checkSign))|(bitXor&(xLeft>>31));
    11.   //返回1有两种情况：符号相同标志位为0（相同）位与y-x 的符号为0（y-x>=0）结果为1；符号相同标志位为1（不同）位与x的符号位为1（x<0）
    12. }

    9. 使用位级运算求逻辑非 !

    /* 
     * 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 
     */

    我们知道-x=(~x)+1,当x>0时，((~x)+1)>>31得1；当x<=0时，((~x)+1)>>31得0。所以我们还要处理x=0和x<0的情况。

    我们可以将x和((~x)+1)进行或运算再右移31位，如果(x | (~x)+1)>>31为0，则说明x等于0；如果(x | (~x)+1)>>31为1，则说明x!=0。

    1. int logicalNeg(int x) {
    2.   return ((x|(~x)+1)>>31)+1;
    3. }

    10. “一个数用补码表示最少需要几位？”

    /* 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
     */

    1. int howManyBits(int x) {
    2.     int y=~x;
    3.     int tmp1=!((1<<31)&x);
    4.     int tmp2=!((1<<31)&y);
    5.     tmp1=~tmp1+1;
    6.     tmp2=~tmp2+1;
    7.  
    8.     int tmp=(tmp1&x)+(tmp2&y);
    9.     
    10.     tmp=tmp|tmp>>1;
    11.     tmp=tmp|tmp>>2;
    12.     tmp=tmp|tmp>>4;
    13.     tmp=tmp|tmp>>8;
    14.     tmp=tmp|tmp>>16;
    15.     int mask=1;
    16.     mask=(mask<<8)|1;
    17.     mask=(mask<<8)|1;
    18.     mask=(mask<<8)|1;  
    19.     int sum=0;
    20.     sum+=tmp&mask;
    21.     sum+=(tmp>>1)&mask;
    22.     sum+=(tmp>>2)&mask;
    23.     sum+=(tmp>>3)&mask;
    24.     sum+=(tmp>>4)&mask;
    25.     sum+=(tmp>>5)&mask;
    26.     sum+=(tmp>>6)&mask;
    27.     sum+=(tmp>>7)&mask;
    28.     return ((sum&0xff)+((sum>>8)&0xff)+((sum>>16)&0xff)+((sum>>24)&0xff))+1;
    29. }

     11.求2*一个浮点数

    /* 
     * 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
     */

    1. unsigned floatScale2(unsigned uf) {
    2.   unsigned sign = uf & 0x80000000;
    3.   unsigned frac = uf & 0x7fffff;
    4.   if(exp ^ 0x7f800000){//exp!=255
    5.      if(!exp){//exp==0
    6.       	frac <<= 1;//此时为非规格化数,尾数无隐含常数1,直接左移1位即可
    7.      }
    8.      else{//0
    9.       	exp += 0x800000;//乘2
    10.       	if((exp ^ 0x7f800000)==0){//判断乘2以后是否溢出      	
    11. 	  frac=0;//输出INF
    12.       	} 
    13.      }
    14.   }
    15.   return sign | exp | frac;
    16. }

     12.将浮点数转化为整数

    /* 
     * 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
     */

    1. int floatFloat2Int(unsigned uf) {
    2.   unsigned INF = 0x80000000;
    3.   //提取符号位
    4.   int s = (uf >>31) & 0x1;
    5.   //提取阶码
    6.   int E = uf >> 23 & 0xff;
    7.   //提取阶数
    8.   int e = E -127;
    9.   if (uf == 0) return 0; 
    10.   //因为输入是规格化浮点数,转化为整数时第23位需要为1
    11.   uf &= 0x00ffffff;
    12.   uf |= 0x00800000; 
    13.   //浮点数中0~22位的数字逻辑上位小数,当看作整数时相当于乘以了2^23
    14.   //阶码为255或阶数大于等于32时,视为溢出,输出INF.因为int为32bit,超出即溢出,且考虑1bit符号位
    15.   if ((uf & 0x7f80000) == 0x7f80000 || e>= 32) return INF;
    16.   if (e<0) return 0;//若为小数,返回零
    17.   //无符号数的移位运算都是逻辑移位 
    18.   if (e <= 23) uf >>= 23 - e;//因为浮点数尾数宽度为23bit,位数小于等于23,尾数位右移.这是一种舍入方式
    19.   else uf <<= e-23;//位数大于23,尾数左移
    20.  
    21.   //当符号位为负数,uf要取值为它的相反数
    22.   if(s) uf = ~uf + 1;
    23.   return uf; 
    24. }

     

    13.求2.0^x

    /* 
     * 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
     */

    1. unsigned floatPower2(int x) {
    2.   //int INF = 0xff << 23;
    3.   int INF = 0x7f800000;
    4.   int exp = x + 127 ;
    5.   //溢出
    6.   if(exp >= 255) return INF;
    7.   //为小数时
    8.   if(exp <= 0) return 0;
    9.  
    10.   return exp<<23;
    11. }

    太痛苦了！真的！后面的三个题等我缓过来再写吧……

    然后，这个答案吧不完全对，有很多小细节我还没来得及一个一个改，还是等我缓过来再写吧……

  • 相关阅读:
    简单汇编教程10 数组
    Scratch软件编程等级考试二级——20191221
    墨天轮专访星环科技刘熙：“向量热”背后的冷思考，Hippo如何打造“先发”优势？
    dreamweaver作业静态HTML网页设计——动漫主题：天宝伏妖录(7页) 学生动漫网页设计作品静态HTML网页模板源码
    【C语言|关键字】C语言32个关键字详解（4）——其他(typedef、sizeof)
    第九章 聚类
    VS2019 第一个驱动程序
    手写RPC框架--7.封装响应
    linux基础1
    【笔试强训选择题】Day41.习题（错题）解析
  • 原文地址：https://blog.csdn.net/zqihm/article/details/127591093