CSAPP-lab1：Data lab

本文最后更新于：2025年6月25日 上午

bitxor

  • 只能使用给定的运算符，得到异或操作的等价函数
  • 类似于数电中与非逻辑门实现异或
  • x xor yt = ~(~(~x&y)&~(x&~y))
1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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));
}

tmin

  • 函数返回二进制补码表示的最小的数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    /* 
     * tmin - return minimum two's complement integer 
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 4
     *   Rating: 1
     */
    int tmin(void) {
      return 1<<31;//tmin is 100....0
    }

isTmax

  • 检测传入的参数x是不是能表示的最大值
  • 若是最大值，那么一定满足：01111111，也即是满足：(x+1)^(~x)的值为0
  • 但是，满足(x+1)^(~x)的并不一定都是01111111，反例：11111111，因此可以利用!!(x+1)作为两者的区分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /*
     * isTmax - returns 1 if x is the maximum, two's complement number,
     *     and 0 otherwise 
     *   Legal ops: ! ~ & ^ | +
     *   Max ops: 10
     *   Rating: 1
     */
    /*x : 01111111
      ~x: 10000000
      y :11111111
      ~y:00000000

    */
    int isTmax(int x) {
      int y=(x+1)^(~x);
      return !y&!!(x+1);
    }

allOddBits

  • 如果奇数比特位上都是1那么函数返回1
  • 使用移位运算得到0xAAAAAAAA，x&y0xAAAAAAAA可以过滤掉所有偶数位，然后将结果与0xAAAAAAAAy异或，如果是0那么满足题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * 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
 */
//0xAAAAAAAA=0b10101010101010101010101010101010
//0x55555555=0b01010101010101010101010101010101
int allOddBits(int x) {
  int a=0xaa;
  int y=(a<<8)+(a<<16)+(a<<24)+a;
  return !((x&y)^y);
}

negate

  • 得到x的负数形式
  • 直接取反加以即可
1
2
3
4
5
6
7
8
9
10
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {//for all x,-x=~x+1
  return ~x+1;
}

isAsciiDigit

  • 判断是不是0-9的数字
  • x应该满足：
    • 大于等于0b00110000
    • 小于 0b00111010
  • 首先判断前四位是不是0011，如果与3异或是0那么说明满足
  • 然后通过与0xf进行与运算的方式，将x去掉last 4 bits，然后减去1010，通过右移31位得到符号位从而判断正负。如果是负数那么说明小于0b00111010，右移31位之后得到的符号位是1；如果是等于或者大于符号位是0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /* 
     * 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:0011 0000  
    //0x3a:0011 1010 
    int isAsciiDigit(int x) {
      int a=!((x>>4)^3);//must be 0011
      int b=(x&0xf)+(~0xa+1);//get the first 4 bits and minus 0b1010
      int c=b>>31;//get the last 1 bit is 0 or 1
      return a&(!!c);
    }

    conditional

  • 实现异或操作（x?y:z）
  • 如果x是1，那么返回y的值，如果x是0，返回z的值
  • 返回(x&y)|(~x&z)即可（x=！！x是为了得到x是0还是1）
1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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;//convert x to 0/1
  x=~x+1;//convert x to complement  0 to 0(0000000...00) ; 1 to -1(1111111....11111)
  return (x&y)|(~x&z);
}

isLessOrEqual

  • 测试是否满足x<=y
  • 有以下情况：
    • x等于y，此时异或得到0
    • x<y
      • 如果x符号位为0y为1那么不满足x<=y
      • 如果x符号位为1y为0那么满足x<=y
      • 如果x符号位和y的符号位相同，那么：
        • 将x减去y，判断结果的正负。在这里为了防止负数减去负数而溢出，使用x+（-y）的形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
// 1:x==y 2:x is neg y is pos 3:x is pos and y is pos 
int isLessOrEqual(int x, int y) {
  int equal=!(x^y);
  int x_flag=!!(x>>31);
  int y_flag=!!(y>>31);
  int minus=x+~y+1;//x-y
  int minus_flag=!!(minus>>31);
  int not_same=!(x_flag^y_flag);
  return equal | (x_flag&!y_flag) | (not_same&minus_flag);
}

logicalNeg

  • 只有当x是0的时候返回1，x为负数或正数都返回0
  • 思路：
    • 当x是0或者最小的负数的情况下，(x^(~x+1))>>31才为0b00…000，其余情况下皆为0b111111…1111，使用这个性质将范围缩小到0或者最小的负数
    • 在满足上面的前提下，排除掉最小负数的情况，即可得到答案
1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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) {
  int y=x^(~x+1);//only if x=000...0000 or x=1000...0000 y=0
  y=(y>>31)+1;//get the sign
  return y&((x>>31)+1);
}

howManybits

  • 题意：使用最少几位补码可以表示一个数字？比如传入一个int类型的x，值为-5，那么它的补码应该是11111111111111111111111111111011，因此最少使用四个bits可以表示也即是1011，1表示符号位。
  • 思路：
    • 可以将负数的情况转化为整数的情况。将负数取反，最终结果不变
    • 找到第一个1出现的位置，然后+1即可。比如howManyBits(12)=howManyBits(01100),1第一次出现在从右往左第四位，加一即使5，也就是最少的可以表示的补码的位数
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      /* howManyBits - return the minimum number of bits required to represent x in
       *             two's complement
       *  Examples: howManyBits(12) = 5           01100
       *            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 b16,b8,b4,b2,b1,b0;
        int musk=x>>31;//musk is all 1 or all 0
        x=(~musk&x)|(musk&~x);//if x is negative ，turn x into ~x
       
        b16=!!(x>>16)<<4;//get the last 16 bits' sign ,and << 4 turn x into 16 or 0,so if x is 16 means in the last 16 bits there is at least 1
        x=x>>b16;//x>>16 or x>>0
        b8=!!(x>>8)<<3;
        x=x>>b8;
        b4=!!(x>>4)<<2;
        x=x>>b4;
        b2=!!(x>>2)<<1;
        x=x>>b2;
        b1=!!(x>>1);
        x=x>>b1;
        b0=!!x;
        return b16+b8+b4+b2+b1+b0+1;
      }

TODO

浮点数部分

CSAPP
CSAPP-lab1：Data lab
http://gls.show/p/6d79108/
作者
郭佳明
发布于
1970年1月1日
许可协议