逆向还原除法有符号非2的幂的第二种优化
从代码上来看,基本和一样,可是0x003F103F
处的加法却很奇怪,请注意0x003F1036
的乘法是否符号乘法,而它的操作数是一个负数,但是实际上我想要的是一个无符号数,所以0x003F103F
处的加法是为了把这个负数变成无符号数。
接下来我们看看它是如何完成这个操作的
0x003F1036
处的88888889实际是FFFFFFFF88888889,它等于88888889-\(2^{32}\)
然后乘以被除数x等于\((88888889-2^{32})*x\)
要想实现\(x*88888889\)就的在0x003F1036
代码的基础上加上\(x*2^{32}等于(88888889-2^{32})*x+x*2^{32} = x*88888889\)(你减了多少份就要加多少份,比如你要+5,但你只能-3,这时候你只需加上个8就行了,减了多少个3就加几个8)
后面就和一样了,
实际上这个汇编代码表示的含义是:
? 从scanf中获取被除数的值,然后除以一个数再打印输出,而这个数等于\(\frac{2^n}{M} = \frac{2^{35}}{0x88888889}=34,359,738,368/2,290,649,225=14.999999996944097802665530336711?\)
而\(\lceil14.999999996944097802665530336711\rceil=15?\)