LI@NG

divpwr2

总结一下我自己做csapp datalab中divpwr2时的跨过的一些坑和思路。

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

看到这个实验我第一反应想到的就是“位移”操作,因为x « n就相当于 x*2^n,同时x » n就相当于 x/2^n, 试验要求中的例子发现,15 » 1 = 7, 但是-33 » 4 = -3 而不是 -2,也就是说对“负数”用位移的方式做除以2^n,之后得到结果是会向“负无穷”方向进的,因为这里的结果应该是 -33/16 = -2.0625,位移直接进到-3,而本实验的要求是我们要向“接近0”的方向“进”,看到这里我的想法是,那就把负数右移后的结果+1,正数的话不变。

按照这个思路,我就在想必须要判断x是正数还是负数,当x是负数的时候生成一个”纠正值”为1,不是负数(也就是0或正数)的话,纠正值就为0,判断是正还是负我是用的如下方法:

int bias = ~(x >> 31) + 1;

因为 int在本实验中是4 bytes = 32 bits,先右移31,如果是负数的话右移后应该是 0xFFFFFFFF,因为有符号最高位负数为1,如果是正数或者0,右移后应该是0,这样再对他们求补码,就能得到负数得1,正数得0.

然后我就有了如下代码:

int divpwr2(int x, int n) {
  int bias = ~(x >> 31) + 1;
  int result = (x >> n) + bias;
  return result;
}

但是测试后发现不对,当测试divpwr2(0x8000000, 0)时,应当返回0x8000000,但我却返回了0x8000000,检查代码不难发现,无论n是如何,只要x是负数,我总是在x右移之后加上bias,这样导致了即使n=0也偏移了,那么ok,继续改代码,因为本实验可以用!,所以就把n是否为0考虑了进去得到:

int divpwr2(int x, int n) {
  int bias = (~(x >> 31) + 1) && !!n;
  int result = (x >> n) + bias;
  return result;
}

这样我们发现divpwr2(0x80000000, 0)测试过了,但是divpwr2(0x80000000, 1)又出错了,郁闷,就是从这里,我花费了一番功夫,我们先看一下,divpwr2(0x80000000, 1)应该返回0xc0000000,而我返回了0xc0000001,我的第一感觉是,肯定又是bias出了问题,在这里不应该+1,而我却又加了1了,我们仔细看一下,0x80000000 的二进制是:
1000 0000 0000 0000 0000 0000 0000 0000
通过我们代码得到 bias = 1, 然后 x»1 之后应该得到:
1100 0000 0000 0000 0000 0000 0000 0000
然后根据我,们代码,我们在后面又加了一个1,导致比正确答案多一个1,那为什么正确答案不能加1呢。

我们先看一下0x8000000的十进制是什么?是-2147483648,然后这个数除以2^1? 我擦,直接等于-1073741824,OMG~~~原来这个除法直接能被2整除啊,那为毛还加1呢?嗯,这就是说,当x为负数“且”不能被2^n整除的时候,我们将x右移之后再加上bias,当x是正数或零或负数但是能被整除的时候,这个时候不能加bias。

ok,那么现在的问题就是怎么判断一个负数能否被整除呢?我先列一下在什么情况下一个负数能被2整除?比如:0, 2, 4 ,6, 8 为结尾的数,但是像1, 3, 5, 7, 9这种数肯定就不能被2整除了,那么这些数在二进制表示有什么规律呢? (以8bits来表示)

0 -> 0000 0000
2 -> 0000 0010
4 -> 0000 0100
6 -> 0000 0110
8 -> 0000 1000

1 -> 0000 0001
3 -> 0000 0011
5 -> 0000 0101
7 -> 0000 0111
9 -> 0000 1001

ok,我们发现末尾是0的都能被2整除,是1的就不行,那么ok,继续修改代码,通过对最后一位是0还是1来判断是否整除:

int divpwr2(int x, int n) {
  int inexact = ~((x << 31) >> 31) + 1;
  int bias = (~(x >> 31) + 1) && !!n && inexact;
  int result = (x >> n) + bias;
  return result;
}

然后运行发现,我擦,又出错了,但是divpwr2(0x80000000, 1)过了,现在出错的是divpwr2(0x80000002, 2),其结果应该是0xe0000001但是我的结果却是e0000000,这就说明,该加bias的时候反而没加了,那为什么呢?可能就是判断“是否整除”的问题上出错了,我的代码可能认为0x80000002 能被4整除所以没加1,而事实上0x80000002不能被4整除。有了思路,开始debug,0x80000002的二进制是:

1000 0000 0000 0000 0000 0000 0000 0010
对应的十进制是:
-2147483646
我们除以4得到:
536870911.5

ok,问题很显然了,所给的x并不能被2^n整除,分析后发现,因为x末尾有一个0,在这种情况下,能被2^1整除,也就是2,验证了一下,确实不假,那我就推测,是不是说明,如果x的后几位二进制“样式”和“除数”一致的话,则x能被该除数整除 (后面事实证明其实这句话不完全对,比如:-2147483642/6 不整除,但是后4位样式一致,但是后面一句是对的),如果把除数直接看成2^n,那么,二进制末尾有n个0就能被2^n整除?比如:0x80000002 后面有一个0,就能被2整除,但不能被4和8整除,验证:

-2147483646/8 = -268435455.75
确实和我们猜测一致,但是根据上面的表,我们也可以继续验证,因为6的末尾也是1个0,应该能被0x80000002整除,验证:
-2147483646/6 = -357913941
验证成功

为了确保正确,在验证一个如果末尾有3个0的,能否被8整除,我们找一个末尾有3个0的数字,比如:0x80000008(十进制:-2147483640),验证:

-2147483640/8 = -268435455

cool,那么我们现在就知道我们代码哪里有错了,因为我们判断被除数x是否能被整除仅仅只根据最后“一位”进行判断,很显然是不对的,我们应该根据传过来的参数n进行判断,被除数x是否能被n整除,根据上面我们的推测可以得知,当x的最后n位全部为0的时候,被除数x能够被2^n整除。所以,目的就是,根据参数n进行判断x是否能被2^n整除。

如果后n位全为0,那么则x能被2^n整除,否则不能,所以现在的任务就是判断后n位是否为0,我的思路是:

int shift = 31 + ~n + 1 //相当于 31 -n,要位移的步数
// c中不支持超过字节位数的移动
// https://stackoverflow.com/a/7401981
// 所以最大31,如果n是0的话,要分两步移完
// 然后再移动回去,取非
int inexact = !!((((x << shift) << 1) >> shift) >> 1);

这样如果后n位全为0的话,inexact是0表示x能被整除,否则是1表示不能被整除,然后更新代码如下(解决方案1):

int divpwr2(int x, int n) {
  int shift = 31 + ~n + 1;
  int inexact = !!((((x << shift) << 1) >> shift) >> 1);
  int bias = (~(x >> 31) + 1) & !!n & inexact;
  int result = (x >> n) + bias;
  return result;
}

结果,一个好消息,一个坏消息,好消息是,代码通过了,坏消息是:

18 operators exceeds max of 15

Oh…允许最多用15个操作符,ok,那现在看一下如何改进一下代码,我发现,在计算能否被整除以及bias的地方浪费了太多操作符,那么这两个步骤能否合并一下呢? 也就是说,在判断能否被整除的前提之下同时又能够得到bias的值,通过搜索发现我们可以用如下作为我们的bias:

int bias = 1 << n + ~0

这里的目的是为了能够构造出最后n位全为1的效果,比如n=3能得到:

0000 0000 0000 0000 0000 0000 0000 0111

这样之后,如果被除数x能被2^n整除的话,那么x的后n位全部为0,这也也就是说x的后三位全部为0,我们用如下算式:

x + bias

如果x能被2^3整除,那么x后3位全为0,那么x+bias之后的结果的后三位会变成111,然后我们需要做的就是将这后3位移走就好了,这样相当于我们并没有加了bias,如果x不能被2^3整除,也就是说后三位中至少有一个1,那么x+bias的结果的“倒数第四位”一定是一个1,也就相当于向第n+1位进了一个1,就相当于我们加了一个bias,表达式如下:

int result = (x + bias) >> n

但是这个时候我们只是考虑的负数的整除与不整除的情况,对于正数,我们的做法就是,不管x能不能被整除,我们bias永远是0,所以判断x是正还是负,很简单,只需将符号位右移31,如果是正则为0,如果是负则为0xffffffff:

int sign = x >> 31;
// 然后得到考虑进正数后的bias
int bias = sign & ((1 << n) + (~0));

所以最终优化后的解决方案2:

int divpwr2(int x, int n) {
  int sign = x >> 31;
  int bias = sign & ((1 << n) + (~0));
  int result = (x + bias) >> n;

  return result;
}

OK…大功告成!