Manipulating Bits

《深入了解计算机》第二章习题

此次DataLab的目的呢，是通过编写一系列函数来熟悉整数、浮点数以及位操作。你会解决一系列的编程puzzle，在你思考的这个过程中，将对位操作有更深刻的理解。关于我的理解可戳这里

任务目标

首先来看我们需要解决的puzzle有哪些：

上手指南

首先，一共有15个需要补充的函数，全部在bits.c文件中进行编写

• 运行 make btest 编译函数
• 使用 dlc compiler (./dlc) 自动检测你的代码是否符合规定
• 运行 ./btest 检测函数是否编写成功
• 使用 ./ishow n 查看n的十六进制，有符号整型和无符号整型形式
• 使用 ./fshow n 查看n的浮点数表示形式

小技巧

• x * 8 => x<<3
• !(x ^ y) => x == y
• -x => ~x + 1
• x != 0 => (!!x)为真
• ……

题目及其解法

bitAnd(x,y)

• 题目要求 ：只用 | 和 ~ 实现 x&y
• 允许操作：~ |
• 操作数限制：8
• 分值：1
• 使用样例：bitAnd(6, 5) = 4

此题运用摩根定律可以解决 :

x&y = ~(~(x&y)) = ~((~x)|(~y))

int bitAnd(int x, int y) {
  return ~((~x) | (~y));
}

getByte(x,y)

• 题目要求 ：从数x中提取从右数的第n个字节 (0<= n <=3)
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：6
• 分值：2
• 使用样例：getByte(0x12345678,1) = 0x56

此题解题思路即为将x右移n个字节，最后返回低八位所得结果。

int getByte(int x, int n) {
  //n * 8
  n = n<<3;
  //x右移8*n位
  x = x >> n;
  //保留最后8位
  return 0xff & x;
}

logicalShift(x,n)

• 题目要求 ：将数x逻辑右移n位 (0 <= n <= 31)
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：20
• 分值：3
• 使用样例：logicalShift(0x87654321,4) = 0x08765432

此题思路为将x右移n位后，清零高n位。

int logicalShift(int x, int n) {
  return (x>>n)&(~((1<<31)>>n<<1));
}

bitCount(x)

• 题目要求 ：返回x对应二进制数中1的个数
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：20
• 分值：4
• 使用样例：bitCount(5) = 2, bitCount(7) = 3

首先将32位数分为8组，对于每四位数，通过三次移位运算统计每组数中1的个数，然后将前16位与后16位相加，将1的个数浓缩在16位中，再以同样的方法将1的个数整理到4位中，得到最后结果。

int bitCount(int x) {
  //Integer constants 0 through 255 (0xFF)
  //令 i = 0x11111111
  int sum = 0;
  int i = 0x11| (0x11 << 8);
  i = i |(i << 16);

  //对于每四位，通过不停的移位运算将前三位的1加到第四位上
  sum += x & i;
  sum += (x >> 1) & i;
  sum += (x >> 2) & i;
  sum += (x >> 3) & i;

  //令i = 0xffff;
  i = 0xff | (0xff<<8);

  //将前16位与后16位相加
  sum = (sum >> 16) + (i & sum);

  //令i = 0x0f0f
  //整理每8位之和
  i = 0x0f | (0x0f<<8);
  sum = ((sum >> 4) & i) + (sum & i);

  //将前8位与后8位相加
  i = 0xff;
  sum = (sum >> 8) + (i & sum);

  return sum;
}

bang(x)

• 题目要求 ：不使用!而计算!x
• 允许操作：~ & ^ | + << >>
• 操作数限制：12
• 分值：4
• 使用样例：bang(3) = 0, bang(0) = 1

此题运用到了一个小技巧，非零数的相反数符号和自身不同，而零的相反数还是零。首先求出x的相反数，再左移取得符号位，与原数符号做按位或运算，若是符号相同得到0，不同得到-1。

int bang(int x) {
  //求x的相反数，利用0的相反数还是0，非零的数与其相反数符号不同的性质
  int opposite_x = ~x + 1;
  //符号相同得到0，不同得到-1
  int bits = (opposite_x >> 31) | (x >> 31);

  return bits + 1;
}

tmin()

• 题目要求 ：返回所能表示的最小整数
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：4
• 分值：1
• 使用样例：tmin() = 0x80000000

此题考查补码所能表示的最小数。

int tmin(void) {
  return 1<<31;
}

fitsBits(x,n)

• 题目要求 ：如果x可以表示为n位二进制补码形式,则返回1，否则返回0
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：15
• 分值：2
• 使用样例：fitsBits(5,3) = 0, fitsBits(-4,3) = 1

若将x左移32-n位再右移回去，若得到的结果与原来的结果相同，则证明x可以用n位二进制补码形式表示。
ps：

• 需注意n位补码可以表示的数值范围为[-2^(n-1) , 2^(n-1) - 1]
  
• 由于系统编译器对于测试代码优化版本的问题，会产生 fitsBits(0x80000000,32) = 0 的测试错误，此时我们可以手动降低编译优化版本，具体的原理可戳这里

int fitsBits(int x, int n) {
  int c = ~n + 33;
  int changedX = x << c;
  int changedY = changedX>> c;

  return !(changedY ^ x); 
}

divpwr2(x,n)

• 题目要求 ：计算x/(2^n)
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：15
• 分值：2
• 使用样例：divpwr2(15,1) = 7, divpwr2(-33,4) = -2

x/(2^n)其实就是将x右移n位，但是在有余数的情况下应该向0取整，整数通过移位能很好地解决这一问题，但是对于负数而言，则应该加1。所以我们用t存取x的符号，tt存取x的后n位数，当负数除不尽有余数时，结果加1。

int divpwr2(int x, int n) {
  //取符号
  int t = x >> 31; 
  int tmp = (1 << n) + ~0;
  //取后n位 
  int tt = tmp & x;
  //取后n位是否有数
  return (x >> n) + ((!!tt) & t);  
}

negate(x)

• 题目要求 ：返回-x
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：5
• 分值：2
• 使用样例：negate(1) = -1.

[-x]反 = ~[x]反
=> [-x]反 + 1 = ~[x]反 + 1
=> [-x]补 = ~[x]反 + 1

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

isPositive(x)

• 题目要求 ：x>0返回1,x<=0返回0
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：8
• 分值：3
• 使用样例：isPositive(-1) = 0.

取m记录x的符号位，(!!x)判断x是否不为零

int isPositive(int x) {
  int m = x >> 31;
  return !m & (!!x);
}

isLessOrEqual(x,y)

• 题目要求 ：x<=y返回1否则返回0
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：24
• 分值：3
• 使用样例：isLessOrEqual(4,5) = 1

返回1的情况有两种：
①x为负数而y为正数
②x、y符号相同且 x-y <= 0

int isLessOrEqual(int x, int y) {
  //y-x
  int m = (~x + 1) + y;
  //取x，y符号
  int p = !!(x>>31);
  int q = !!(y>>31);

  return (!(m>>31)&(!(p^q))) | (p&!q);
}

ilog2(x)

• 题目要求 ：返回不超过以2为底x对数的最小整数
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：90
• 分值：4
• 使用样例：ilog2(16) = 4

寻找不超过以2为底x对数的最小整数就是寻找x的二进制形式中最高位1出现的位置。

int ilog2(int x) {
  //记录最高位1的位置
  int result1,result2,result3,result4,result5,flag;
  //判断高16位是否有1出现
  flag = !!(x >> 16);
  //出现1则确定最终结果数量级必然大于16
  result1 = flag << 4;
  //继续判断高8位是否有1出现，以此类推
  x = x >> result1;

  flag = !!(x >> 8);
  result2 = flag << 3;
  x = x >> result2;

  flag = !!(x >> 4);
  result3 = flag << 2;
  x = x >> result3;

  flag = !!(x >> 2);
  result4 = flag << 1;
  x = x >> result4;

  flag = !!(x >> 1);
  result5 = flag << 0;
  x = x >> result5;

  return result5 + result4 + result3 + result2 + result1;
}

float_neg(uf)

• 题目要求 ：返回和浮点数参数-f相等的二进制数，返回参数本身当参数是NaN时
• 允许操作：包括任何整型/无符号整型操作，||，&&以及if，while
• 操作数限制：10
• 分值：2
• 使用样例：float_neg(0) = 0x80000000

对于一个浮点数来说，指数部分全为1时，若尾数部分不全为0（不需要考虑符号位），则表示这个数不是一个数（NaN），在排除了NaN的情况后，只需将符号位取反即可。

unsigned float_neg(unsigned uf) {
  unsigned temp;
  //最高位取反
  temp = uf ^ 0x80000000;
  //E全为1。这时，如果有效数字M全为0，表示±无穷大（正负取决于符号位s）；
  //如果有效数字M不全为0，表示这个数不是一个数（NaN），符号位无关紧要。
  //最高位清零
  int t = uf & 0x7fffffff;
  if(t > 0x7f800000)
    return uf;
  return temp;
}

float_i2f(x)

• 题目要求 ：实现(float)x，返回x对应浮点数的二进制表示形式
• 允许操作：包括任何整型/无符号整型操作，||，&&以及if，while
• 操作数限制：30
• 分值：4
• 使用样例：float_i2f(0x800000) = 0x4b000000

此题考查对于IEEE二进制浮点数算术标准（IEEE 754）的掌握

• 用s来保存符号位
• exp记录最高位的位置，即记录指数
• franc记录尾数
  

最后返回x对应的浮点数的32位754标准的二进制存储格式。

unsigned float_i2f(int x) {
  unsigned s = 0, exp = 31, frac = 0, d = 0;
  if (x == 0x00000000u) return 0x00000000u;
  if (x & 0x80000000u) { s = 0x80000000u; x = -x; }
  while (1) {
    if (x & 0x80000000u) break;
    //exp记录最高位的位置
    exp -= 1;
    x <<= 1;
  }
  //最后舍掉的8位若最高位为1且低七位仍有数，要进位
  if ((x & 0x000001ff) == 0x180) d = 1;
  else if ((x & 0xff) > 0x80) d = 1;
  //franc记录尾数
  frac = ((x & 0x7fffffffu) >> 8) + d;
  
  return s + ((exp + 127) << 23) + frac;
}

float_twice(uf)

• 题目要求 ：返回以unsinged表示的浮点数二倍的二进制形式
• 允许操作：包括任何整型/无符号整型操作，||，&&以及if，while
• 操作数限制：30
• 分值：4
• 使用样例：float_twice(0x7f800000) = 0x7f800000

返回结果：

• 若数为NaN，仍返回其本身
• 溢出情况0x80000000时返回0x80000000
• 若指数尚为0时，通过左移得到二倍形式
• 否则在指数位上加1，即加上0x00800000

unsigned float_twice(unsigned uf) {
  // 若是指数为0情况
  if((uf & 0x7F800000) == 0)
    return (uf << 1) | (0x80000000 & uf);//特殊情况0x80000000
  //若数为NaN
  else if((uf & 0x7fffffff) >= 0x7f800000)
    return uf;
  return uf + 0x00800000;
}

总结

本次DataLab在种种运算符限制下实现了一些基本操作，相信做完的你对数据的理解又加深啦~