博客

计算机基础datalab

  • Post author:
  • Post category:其他




datalab



目录

  1. bitXor
  2. thirdBits
  3. fitsShort
  4. isTmax
  5. fitsBits
  6. upperBits
  7. anyOddBit
  8. byteSwap
  9. absVal
  10. divpwr2
  11. float_neg
  12. logicalNeg
  13. bitMask
  14. isGreater
  15. logicalShift
  16. satMul2
  17. subOK
  18. trueThreeFourths
  19. isPower2
  20. float_i2f
  21. howManyBits
  22. float_half



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);
    }

将(x&y)看作矩阵[1,0],[0,0],

(~ x & ~ y)看作矩阵[0,0],[0,1],目标矩阵[0,1],[1,0],因此~ (~ x & ~ y) & ~ (x & y)可以得到目标矩阵



thirdBits

  • thirdBits – return word with every third bit (starting from the LSB) set to 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 8
  • Rating: 1 
    int thirdBits(void) {
        int r =0x49;
        r = r|(r<<9);
        r = r|(r<<15);
        return r;
    }

开始时为1001001，经过第一步后变为18位，此时只需在添加5个1，运用|的特性，

左移15位此时r的第一个1与r<<15的最后一个1重合，得到值



fitsShort

  • fitsShort – return 1 if x can be represented as a
  • 16-bit, two’s complement integer.
  • Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 8
  • Rating: 1 
    int fitsShort(int x) {
        x = x >> 15;
        x = x ^ (x >> 16);
        return !x;
    }

分两种：

1.范围之内的正负数——判断17到32位是否一样。

2.在int范围为正short为负的数——还要判断第16位是否等于第32位



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) {
    int r = x+1;
    return !(r+r+!r);
}

利用当x最大时r = x+1 = 0x80000000,r+r = 0,



fitsBits

  • fitsBits – return 1 if x can be represented as an
  • n-bit, two’s complement integer.
  • 1 <= n <= 32
  • Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2 
int fitsBits(int x, int n) {
    int a = n + 31;//等于n-1
    int b = x >> 31;
    x = x >> a;
    x = x ^ b;
    return !x;
}

分正数与负数，考虑32位为符号位

  1. 当x为正数时,右移n-1位后等于0x00000000
  2. 当x为负数时,右移n-1位后等于0xffffffff



upperBits

  • upperBits – pads n upper bits with 1’s
  • You may assume 0 <= n <= 32
  • Example: upperBits(4) = 0xF0000000
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 10
  • Rating: 1 
int upperBits(int n) {
    return ((!!n)<<31)>>(n+(~0));
}

先判断n是否为0,是则!!n = 0;不是则n = 1;在左移至32位,此时0x80000000,在通过32位为1右移后也为1将剩余位数设0



anyOddBit

  • anyOddBit – return 1 if any odd-numbered bit in word set to 1
  • Examples anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 2 
int anyOddBit(int x) {
    int a = 0xAA | 0xAA << 8;
    a = a | a << 16;
    return !!(x&a);
}

建立一个32位的偶数位为1的数，偶数位与0&，奇数与1&，如果为0，则没有，反之



byteSwap

  • byteSwap – swaps the nth byte and the mth byte
  • Examples: byteSwap(0x12345678, 1, 3) = 0x56341278 
  •        byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
  • You may assume that 0 <= n <= 3, 0 <= m <= 3
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 25
  • Rating: 2 
int byteSwap(int x, int n, int m) {
    int temp = 0xff;
      n = n << 3;
      m = m << 3;
      int mxorn = ((x >> n) ^ (x >> m)) & temp;//防止出现意外
      x = x ^ ((mxorn << m) | (mxorn << n));
      return x;
}



absVal

//利用 ^ 运算的半加性，a ^ (a ^ b) = b; b ^ (a ^ b) = a

  • absVal – absolute value of x
  • Example: absVal(-1) = 1.
  • You may assume -TMax <= x <= TMax
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 10
  • Rating: 4 
int absVal(int x) {
    int val = x>>31;
    return (x^(val))+((val)&1);//x^(val)当x正，取x本身，为负，取x反数。(val)&1 x正取0，x负取1
}

分两种情况：x为正或x为负。x为负时需要取反加1



divpwr2

  • divpwr2 – Compute x/(2^n), for 0 <= n <= 30
  • Round toward zero
  • Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2 
int divpwr2(int x, int n) {
    return (x+(x>>31&((1<<n)+~0)))>>n;
}

当x>0，x/(2^n) = x>>n;当x<0，则小数部分大于0时需要x+(1<<n)+~0)之后在进行移位操作



float_neg

  • float_neg – Return bit-level equivalent of expression -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 representations of
  • single-precision floating point values.
  • When argument is NaN, return argument.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 10
  • Rating: 2 
unsigned float_neg(unsigned uf) {
    unsigned ans = uf^0x80000000;
    unsigned nan = uf&0x7fffffff;
    if (nan>0x7f800000)//是否为nan
        return uf;
    return ans;
}

因为float的正负只与第32位有关不涉及补码,所以用^0x80000000可以完美实现取负操作；

再者排除题目所提及的NAN的情况



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) {
    return ~(x|(~x+1))>>31&1;
}

利用只有0的补码为0，将x与x的补码相或，判断是不是x为0,为0则~ (x|(~x+1))>>31等于1，不为0则等于0



bitMask

  • bitMask – Generate a mask consisting of all 1’s
  • lowbit and highbit
  • Examples: bitMask(5,3) = 0x38
  • Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
  • If lowbit > highbit, then mask should be all 0’s
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 16
  • Rating: 3 
int bitMask(int highbit, int lowbit) {
  return ((~0)<<lowbit)&((~0)+(2<<highbit));
}

(~ 0)<<lowbit将lowbit位归0，在与(~0)+(2<<highbit)将highbit位归0；剩下及所求



isGreater

  • isGreater – if x > y then return 1, else return 0
  • Example: isGreater(4,5) = 0, isGreater(5,4) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 24
  • Rating: 3 
int isGreater(int x, int y) {
    int a = (x^y) >> 31;
    int b = x+~(a|y);
    return !(b>>31);
}
  1. 求x与y的符号是否相同，相同a=0x00000000,不同a=0xffffffff
  2. 当x与y符号相同时 b=x-y-1 (因为 x==y 时 return 0) 符号不同时 b = x
  3. 判断b的符号，为1表示 x<=y 为0 表示 x>y



logicalShift

  • logicalShift – shift x to the right by n, using a logical shift
  • Can assume that 0 <= n <= 31
  • Examples: logicalShift(0x87654321,4) = 0x08765432
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 3 
int logicalShift(int x, int n) {
    int mask_ = (~0)+(2<<(32+~n));//32+~n是为了防止溢出
    return (x>>n)&mask_;
}

//只需同时考虑x<0的情况；将[31-n+1,31]位变为0，在&x>>n



satMul2

  • satMul2 – multiplies by 2, saturating to Tmin or Tmax if overflow
  • Examples: 
  •         satMul2(0x30000000) = 0x60000000

  •         satMul2(0x40000000) = 0x7FFFFFFF (saturate to TMax)

  •         satMul2(0x60000000) = 0x80000000 (saturate to TMin)
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 3 
int satMul2(int x) {
    int a=x<<1;//*2操作
    int b=x>>31;//符号位
    int c=(x^a)>>31;//判断是否超过Tmax或Tmin,为0xffffffff表示超了
    int tmin=1<<31;
    return ((~c)&a)+(c&(~b+tmin));//(~c)&a在超过int表示时进行"归0"操作,
    //c&(~b+tmin)中c用来判断是否需要表示为Tmax或Tmin;当x为正时~b+tmin表示tmin-1
}

对x进行<<1实现x

2操作;由于超过int表示范围x的符号位会与x

2不同，以此判断返回值



subOK

  • subOK – Determine if can compute x-y without overflow
  • Example: 
  •        subOK(0x80000000,0x80000000) = 1,

  •        subOK(0x80000000,0x70000000) = 0,
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 3 
int subOK(int x, int y) {
    int a = x + (~y + 1);
    int b = x ^ y;
    int c = a ^ x;
    return !((b & c) >> 31);
}

判断要同时满足两个条件，x与y符号不同，x与x-y符号不同的时候返回0



trueThreeFourths

  • trueThreeFourths – multiplies by 3/4 rounding toward 0,
  • avoiding errors due to overflow
  • Examples: trueThreeFourths(11) = 8 
  •         trueThreeFourths(-9) = -6

  •         trueThreeFourths(1073741824) = 805306368 (no overflow)
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 4 
int trueThreeFourths(int x)
{
    int y=x&0x3;//判断/4后的1，2位 0.75 0.5 0.25
    x=x>>2;
    return (x<<1)+((y+y+y+((x>>31)&0x3))>>2)+x;
}

思路为1/4

x + 1/2

x + 四舍五入

判断是否为4的倍数，若不是当

  1. 小于4时，
  2. x为正数且大于4，四舍五入；
  3. x为负数，8需要四舍五入



isPower2

  • isPower2 – returns 1 if x is a power of 2, and 0 otherwise
  • Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
  • Note that no negative number is a power of 2.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 20
  • Rating: 4 
int isPower2(int x) {
  return ((!(x&(x+~0))) & ((~(x>>31)&(!!x))));
}

利用当x = 2^n，则x-1的[0,n-1]位都为1;判断是否为正和x-1的0到n-1位（未知）是否全等于1



float_i2f

  • 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) {
    int s,h,exp,f,flag;
    unsigned temp,result;
    if(!x)
    return x;             //由于规范数情况不包含0，所以先处理0情况。
    s=(x>>31)&0x01;
    if(s)
    x=~x+1;              //获得符号位，并将x变为正值。
    h=0;
    temp=x;
    while(!(temp&0x80000000))
    {
     temp<<=1;
     h++;
    }                    //获得x的最高有效位，即确定fraction的位数。
    temp=temp<<1;
    exp=127+31-h;  //根据单精度浮点数规则计算出exp，和fraction位数。
    f=31-h;
    flag=0;               //进行向偶舍入
    if((temp&0x1ff)>0x100)
    flag=1;              //出现在规定位置后大于0b100的情况就进1.
    if((temp&0x3ff)==0x300)
    flag=1;              //出现最后一位为1，且下一位为1的情况也进1(向偶取整)
    result=(s<<31)+(exp<<23)+(temp>>9)+flag;//计算最终结果
    return result;
}

确认是否能正常转为float，排除不规范，0，和无穷的情况，操作如上图



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 temp = x ^ (x << 1);//将负数转为正数相同的判别，同时加一个符号位(只能用32位才能表示的数不用加)
    int bit_16,bit_8,bit_4,bit_2,bit_1;
    bit_16 = !!(temp >> 16) << 4;//判断长度是否大于16
    temp = temp >> bit_16;、//对折操作
    bit_8 = !!(temp >> 8) << 3;//同上
    temp = temp >> bit_8;
    bit_4 = !!(temp >> 4) << 2;
    temp = temp >> bit_4;
    bit_2 = !!(temp >> 2) << 1;
    temp = temp >> bit_2;
    bit_1 = !!(temp >> 1);
    return 1 + bit_1 + bit_2 + bit_4 + bit_8 + bit_16;
}

对折法，分4次对折，每次的长度可以对折就将x对折一半，直到折成 1bit 为止，最后用 1(bit) 加上折掉的长度

因为符号位始终都要站一个格子，所以不是只能用32位表示的都要加1位



float_half

  • float_half – Return bit-level equivalent of expression 0.5*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_half(unsigned uf) {
    unsigned s=uf&0x80000000;//取符号位
    unsigned exp=uf&0x7f800000;//取31到23位
    int lsb=((uf&3)==3);//31，32两位是否都为1，用于补位
    if (exp==0x7f800000)//无穷
        return uf;
    if (exp<=0x800000)//*0.5后不规范
        return s|(((uf^s)+lsb)>>1);
    if (exp)//正常
        return (uf-0x800000);
}

判断能否正常除以2；无穷，*0.5后不规范单独操作


版权声明：本文为weixin_60827029原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。