求助!! 关于ulldiv的实现
对于64位无符号除法, vc调用一个库函数_ulldiv来实现,
原代码在rtl/intel/ulldiv.asm有实现,简单描述成c语言就是这样的
假设a,b,c都是64位数, 那么要求c = a/b
a' = a;
b' = b;
if (b' < 0x100000000)
{
return a'/b'; //因为如果b能用一个dword表示, 那么可以edx:eax div ecx实现
}
while(b >= 0x10000000) //否则， 就把b和a同时右移, 移动到b能放到一个dword结束
{
b' >>= 2;
a' >>= 2;
}
c = a'/b'; // 这个时候,再次可以用edx:eax div ecx来实现.
if (c*b > a) --c; // 如果c*b比a要大的话, 说明刚得到的c比实际的c要少一.
return c;
其实算法很巧妙， 而且人也非常容易理解.
我把2个数都缩小一点, 然后来除,
但问题是:
怎么证明这个都缩小以后算出来的c就比原来的c大1, 或者跟原来的c一样的大?
ps: 这个问题困惑了我1个月, 天天晚上就是想办法证明,
但总是做不出来. 现在睡觉都睡不好了. 帮我解决下， 另外我在送100分.
[解决办法]
证明如下：
c=a/b=(a'N+a0)/(b'N+b0)<=(a'N+N-1)/(b'N)=(a'+(N-1)/N)/b'=c'
c=a/b=(a'N+a0)/(b'N+b0)>=(a'N)/(b'N+N-1)=c'/(1+(N-1)/(b'N))
c+c*(N-1)/(b'N)>=c' (1)
注意到b'>=2^31
如果b>=2^33
c=a/b<=2^64/2^33=2^31<=b'
c*(N-1)/(b'N)<=1 则 c+1>=c' (2)
如果b<2^33 那么移一位就可以了，也就是N=2
c=a/b<=2^64/2^32=2^32
c*(N-1)/(b'N)=c/(2b')<=2^32/(2*2^31)=1
也可以得出 c+1>=c' (2)
综合 （1），（2）， c=<c'<=c+1
也是 把c'=c, 或者 c'=c+1 就可以了
