《深入理解计算机系统/CSAPP》

isTmax(int x)
minusOne(void)
upperBits(int n)
copyLSB(int x)
anyOddBit(int x)
getByte(int x, int n)
implication(int x, int y)
mult3div2(int x)
isAsciiDigit(int x)
logicalAnd(int x, int y)
multFiveEighths(int x)
rotateRight(int x, int n)
satMul3(int x)
float_add(unsigned ufx, unsigned ufy)
isNonZero(int x)
leftBitCount(int x)
float_f2i(unsigned uf)

更加全面的参考:http://www.hh-yzm.com/index.php/archives/6/

/*
isTmax - 如果x是最大的二进制补码,返回1;否则返回0
 *   允许的操作符: ! ~ & ^ | +
 *   最多操作符数目: 10
 *   分值: 2*/
int isTmax(int x) {
   return !((x^(~(x+1))))&(!!(~x));
 //return !((x^(~(x+1)))|(!(~x)));
}

int isTmax(int x) {
 return (!(x+1+x+1))&(!!(x+1));
}

分析:
第一种方法:判断相等使用异或操作。x满足x == ~(x+1),排除同样满足条件的0xffffffff(-1)
第二种方法:最大值为0x7fffffff,加一会变为0x80000000,而此数加上本身后会变为0,本身加本身为0的数只有0和0x80000000,然后再将0xffffffff(-1)排除即可。

/*
 * minusOne - return a value of -1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int minusOne(void) {
  return ~0;
}

int minusOne(void){
  return return (1 << 31) >> 31;
}

分析:返回0xffffffff (-1),即~0。
或者先左移31位变成0x80000000然后在右移31位就变成-1了。

/*
 * 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个二进制位设置为1
传入0的时候结果会是零
为了减少分类讨论,我们要做到把零和非零的数并行操作,使用!!n
作为要操作的基准数
如果传入的不是零 这个基准数变成了1
如果是零 ,则变成了 0 (怎么操作结果都会为零)
先将!!n<<31,使得其位于最顶端
之后右移n-1位,这样总位数 = n - 1 + 1 = n位
由上题可知~0 = -1

/*
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
  return (x<<31)>>31;
}

分析:将二进制数所有位的数置为最低位数
使用算数右移来拓展最低位。需将最低位放在最高位x<<31。

/*
 * 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 mask = 0xAA | 0xAA << 8;
  mask = mask | mask << 16;
  return !!(x&mask);
}

分析:判断一个二进制数任意奇数位是否有1
0xAA 位 1010,当中所有的1都在奇数位,所有的0都在偶数位,
则与x按位与,因为0&1=0,所以只要奇数位有一个1,就会出现1,偶数位0&任何数都是0。
由于是32位的,又因为数值有规定不能超过256,不能直接用0xAAAAAAAA,所以要先将0xAA(170)扩展到32位,(先从4位扩张到16位然后扩展到32位)。

/*
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
  return ((x >> (n << 3)) & 0xFF);
}

分析:获取x的第n字节
1byte=8bit,直接右移n << 3位 取字节 n & 0xFF

/*
 * implication - return x -> y in propositional logic - 0 for false, 1
 * for true
 *   Example: implication(1,1) = 1
 *            implication(1,0) = 0
 *   Legal ops: ! ~ ^ |
 *   Max ops: 5
 *   Rating: 2
 */
int implication(int x, int y) {
    return (!x)|(!!y);
}

分析:离散数学蕴含表达式p→q即 ┐p∨q

/*
 * mult3div2 - multiplies by 3/2 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/2),
 *   including overflow behavior.
 *   Examples: mult3div2(11) = 16
 *             mult3div2(-9) = -13
 *             mult3div2(1073741824) = -536870912(overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int mult3div2(int x) {
    int y = (x << 1) + x;
    return (y >> 1) + (((y >> 31)&1)&(((y << 31)>>31)&1));
}

分析:实现x*3/2

/*
 * 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) {
  return (!((x+(~0x30+1))>>31)) & (!!((x+(~0x3a+1))>>31));
}

分析:判断字符是否是ASCII码中的数字
即判断x是否在0x30-0x39,即x减去对应范围值后,判断其符号位是否为0或1。
当0x30 <= x <= 0x39时
&左边的值可能为0或者正数 最高为0
&右边的值肯定为负数 最高位只能1
所以前者加一个!后者要加两个!!

/*
 *   logicalAnd - x && y
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int logicalAnd(int x, int y) {
  return !!x & !!y;
}

分析:按位与运算

/*
 * multFiveEighths - multiplies by 5/8 rounding toward 0.
 *   Should exactly duplicate effect of C expression (x*5/8),
 *   including overflow behavior.
 *   Examples: multFiveEighths(77) = 48
 *             multFiveEighths(-22) = -13
 *             multFiveEighths(1073741824) = 13421728 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */
int multFiveEighths(int x) {
  int mult = (x << 2) + x; // 5*x
  int sign = (mult >> 31); // 提取符号位
  int neground = ((mult + 7) >> 3) & sign; //四舍五入
  return neground + ((mult & ~sign) >> 3);
  //取舍入结果,如果符号为1(负),则返回
  //只是舍入的部分,如果不是,则仅返回
  //return语句的后半部分,其中我们除以8。
}

分析:x*5/8

/*
 * rotateRight - Rotate x to the right by n
 *   Can assume that 0 <= n <= 31
 *   Examples: rotateRight(0x87654321,4) = 0x18765432
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 25
 *   Rating: 3
 */
int rotateRight(int x, int n) {
 int a, x2, x3, negN;
    negN = ~ n + 1;
    a = ~ (~ 0 << (32 + negN));
    x2 = x >> n;
    x3 = x << (32 + negN);
  return (x2 & a) | x3;
}

分析:循环右移n位
构造低n位为1的掩码,用&获取移出位,用|补齐补充位。

/*
 * satMul3 - multiplies by 3, saturating to Tmin or Tmax if overflow
 *  Examples: satMul3(0x10000000) = 0x30000000
 *            satMul3(0x30000000) = 0x7FFFFFFF (Saturate to TMax)
 *            satMul3(0x70000000) = 0x7FFFFFFF (Saturate to TMax)
 *            satMul3(0xD0000000) = 0x80000000 (Saturate to TMin)
 *            satMul3(0xA0000000) = 0x80000000 (Saturate to TMin)
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 3
 */
int satMul3(int x) {
   int x2 = x << 1;
   int x3 = x2 + x;
   int sign = x >> 31;
   int tmin = 1 << 31;
   int g = ((x^x2)|(x^x3))>>31;
   return ((~g)&x3)+(g&(tmin+(~sign)));
}

分析:x*3

/*
 * isNonZero - Check whether x is nonzero using
 *              the legal operators except !
 *   Examples: isNonZero(3) = 1, isNonZero(0) = 0
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int isNonZero(int x) {
  return (x|(~x+1))>>31&1;
}

分析:不使用!操作,判断x==0
利用+0/-0最高位为0,而负数最高位为1,将正数转换为负数判断。

/*
 * leftBitCount - returns count of number of consective 1's in
 *     left-hand (most significant) end of word.
 *   Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 50
 *   Rating: 4
 */
int leftBitCount(int x) {
  int cnt = 0;
    int off = 1&(!(~x));
    cnt += (!!(~(x>>16)))<<4;
    cnt += (!!(~(x>>(cnt+8))))<<3;
    cnt += (!!(~(x>>(cnt+4))))<<2;
    cnt += (!!(~(x>>(cnt+2))))<<1;
    cnt += (!!(~(x>>(cnt+1))));
    return 32+~cnt+off;
}

分析:返回二进制数从高位到低位,连续为1的个数
若二进制数x>>n,为0xffffffff,那么可以说明其[n,31]位上的数为全1,只要找出这个最大的数n,本题答案即为31-n=31+~n+1
若n=0时有两种情况,0xffffffff和0xfffffffe,需要区别。

/*
 * float_f2i - 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
 */
/*
将浮点数转换为有符号整数,float_f2i
说明:超出整形范围(NaN和无穷大)返回0x80000000
限制操作:所有整数相关操作 || && if while
操作数量:30
难度:4
*/
int float_f2i(unsigned uf) {
  int s_    = uf>>31;
   int exp_  = ((uf&0x7f800000)>>23)-127;
   int frac_ = (uf&0x007fffff)|0x00800000;
   if(!(uf&0x7fffffff)) return 0;

   if(exp_ > 31) return 0x80000000;
   if(exp_ < 0) return 0;

   if(exp_ > 23) frac_ <<= (exp_-23);
   else frac_ >>= (23-exp_);

   if(!((frac_>>31)^s_)) return frac_;
   else if(frac_>>31) return 0x80000000;
   else return ~frac_+1;
}

分析:
先将浮点数分成三段,符号部分s = uf>>31,指数大小exp = ((uf&0x7f800000)>>23)-127,获取小数部分,并补上浮点数缺省的1,frac_ = (uf&0x007fffff)|0x00800000。

处理特殊情况全为0是返回0,若指数大于31,整数无法表示溢出返回0x80000000。若指数小于0,该数0<x<1返回0。

若指数部分大于23则将小数部分向左移动frac <<= (exp - 23) ,exp_代表指数大小。

若指数部分小于23则将小数部分向右移动frac >>= (23 - exp) ,exp_代表指数大小。

考虑最后符号,正数转换为负数不会产生溢出。若frac_为正数,则根据s_调整正负输出即可。

若frac_为负数,唯一正确情况为0x80000000。

点赞
  1. 超哥说道:
    Sogou Explorer Windows 10

    牛逼

发表评论

电子邮件地址不会被公开。必填项已用 * 标注