比较两个可能溢出的倍数

{ 返回false; } return（（UInt64.MaxValue / a）< b ）; 但它仍然无法帮助我确定ab cd。我是否有任何关于如何确定这一点的想法？谢谢。 嗯，你想把它们分成几小块，分成32位块，并检查这些是否是。首先是一些理论。比如，n = 2 ^ 32，那么 a = a0 + a1 * n b = b0 + a2 * n c = c0 + c1 * n d = d0 + d1 * n （a0 + a1 * n）*（b0 + b1 * n） - （c0 + c1 * n）*（d0 + d1 * n）0 a0 * b0 + a0 * b1 * n + a1 * b0 * n + a1 * b1 * n * n> c0 * d0 + c0 * d1 * n + c1 * d0 * n + c1 * d1 * n ^ 2 0 a0 * b0 +（a0 * b1 + a1 * b0）* n + a1 * b1 * n * n> c0 * d0 +（c0 * d1 + C1 * d0）* n + c1 * d1 * n * n 现在你要总是如何比较数字，比如321 175.你首先 比较最高位数。如果他们不平等，你有 答案。如果它们相等，则比较第二个数字，依此类推， 等等。 这里你也是这样做的。如果a1 * b1 c1 * d1，则结果为真。如果 a1 * b1< c1 * d1，则结果为false。如果两者相等，你转向比较下一个数字，即你比较 a0 * b1 + a1 * b0与c0 * d1 + c1 * d0，等等。 UInt64 a0 = a& 0xFFFFFFFF; UInt64 a1 = a> 32; UInt64 b0 = b& 0xFFFFFFFF; UInt64 b1 = b> 32; UInt64 c0 = c& 0xFFFFFFFF; UInt64 c1 = c> 32; UInt64 d0 = d& 0xFFFFFFFF; UInt64 d1 = d> 32; UInt64 x00 = a0 * b0; UInt64 x01 = c0 * d0; //这个可能会溢出，所以将它们分得更多： int x10 =（a0 * b1）& 1 +（a1 * b0）& 1; //较低位 int x11 =（c0 * d1）& 1 +（c1 * d0）& 1; //较低位 UInt64 x20 = a0 * b1 / 2 + a1 * b0 / 2; //前63位 UInt64 x21 = c0 * d1 / 2 + c1 * d0 / 2; //前63位 if（x10 = 2） { x20 ++; x10 = 0; } if（x11 = 2） { x21 ++; x11 = 0; } 字节x20 = UInt64 x30 = a1 * b1; UInt64 x31 = c1 * d1; 现在如果比较较高的部分，较低的位不重要， 除非较高的部分相等。所以你可以这样做： if（x30 x31） 返回true; else if（x30< x31） 返回false; else if（x20 x21） 返回true; else if（x20< x21 ） 返回false; else if（x10 x11） 返回true; else if（x10< ; x11） 返回false; else if（x00 x01） 返回true; else 返回false; FWIW，这不会溢出。每个部分x00 - x31都在UInt64 范围内。 - Rudy Velthuis http://rvelthuis.de "全世界的问题是傻瓜和狂热分子总是如此肯定，但是那些更加聪明的人充满了...... b $ b怀疑。 - Bertrand Russell 非常有帮助和信息丰富。谢谢，鲁迪。 SteveT I have three values:UInt64 a, b, c, d;I need to determine if: (a*b) <=(c*d). Naturally, just doing themultiplication and comparing would tell me the result. However, thevalues could potentially overflow. For example, if:a = UInt64.MaxValue;b = 2;c = UInt64.MaxValue / 3;d = 4;I still need to be able to conclude ab cd. I can determine ifwrapping will occur on multiplication by doing:if (a <= 1 || b <= 1){return false;}return ((UInt64.MaxValue / a) < b);But it still doesn''t help me determine ab cd. Anybody have anythoughts on how I could determine this? Thanks. 解决方案 On Fri, 03 Oct 2008 16:35:06 -0700, <ag*******@gmail.comwrote:I have three values:UInt64 a, b, c, d;I need to determine if: (a*b) <=(c*d). [...]I''m not aware of anything built into .NET that would do this directlywhile handling overflow. If you were dealing with signed 64-bit values,you could have used the Math.DivRem(), comparing a/c against d/b(including remainder). But with unsigned 64-bit values, I think you mightas well just do the math the long way.Peteag*******@gmail.com wrote:I have three values:UInt64 a, b, c, d;I need to determine if: (a*b) <=(c*d). Naturally, just doing themultiplication and comparing would tell me the result. However, thevalues could potentially overflow. For example, if:a = UInt64.MaxValue;b = 2;c = UInt64.MaxValue / 3;d = 4;I still need to be able to conclude ab cd. I can determine ifwrapping will occur on multiplication by doing:if (a <= 1 || b <= 1){ return false;}return ((UInt64.MaxValue / a) < b);But it still doesn''t help me determine ab cd. Anybody have anythoughts on how I could determine this? Thanks.Well, you want to split them up a bit, into 32 bit chunks, and checkthese. First some theory. Say, n = 2^32, thena = a0 + a1*nb = b0 + a2*nc = c0 + c1*nd = d0 + d1*n(a0 + a1*n)*(b0 + b1*n) - (c0 + c1*n)*(d0 + d1*n) 0a0*b0 + a0*b1*n + a1*b0*n + a1*b1*n*n >c0*d0 + c0*d1*n + c1*d0*n + c1*d1*n^2 0a0*b0 + (a0*b1 + a1*b0)*n + a1*b1*n*n >c0*d0 + (c0*d1 + C1*d0)*n + c1*d1*n*nNow you do how you always compare numbers, like 321 175. You firstcompare the highest digits. If they are not equal, you have youranswer. If they are equal, you compare the second digits, and so on,and so forth.Here you do the same. if a1*b1 c1*d1, then the result is true. Ifa1*b1 < c1*d1, then the result is false. And if both are equal, youturn to comparing the next "digit", i.e. you comparea0*b1 + a1*b0 with c0*d1 + c1*d0, etc.etc.UInt64 a0 = a & 0xFFFFFFFF;UInt64 a1 = a >32;UInt64 b0 = b & 0xFFFFFFFF;UInt64 b1 = b >32;UInt64 c0 = c & 0xFFFFFFFF;UInt64 c1 = c >32;UInt64 d0 = d & 0xFFFFFFFF;UInt64 d1 = d >32;UInt64 x00 = a0*b0;UInt64 x01 = c0*d0;// this one may overflow, so split them up even more:int x10 = (a0*b1) & 1 + (a1*b0) & 1; // lower bitint x11 = (c0*d1) & 1 + (c1*d0) & 1; // lower bitUInt64 x20 = a0*b1/2 + a1*b0/2; // top 63 bitsUInt64 x21 = c0*d1/2 + c1*d0/2; // top 63 bitsif (x10 = 2){x20++;x10 = 0;}if (x11 = 2){x21++;x11 = 0;}Byte x20 =UInt64 x30 = a1*b1;UInt64 x31 = c1*d1;Now if the higher parts are compared, the lower bits don''t matter,except if the higher parts are equal. So you can do:if (x30 x31)return true;else if (x30 < x31)return false;else if (x20 x21)return true;else if (x20 < x21)return false;else if (x10 x11)return true;else if (x10 < x11)return false;else if (x00 x01)return true;elsereturn false;FWIW, this will not overflow. Each part, x00 - x31, is in the UInt64range.--Rudy Velthuis http://rvelthuis.de"The whole problem with the world is that fools and fanatics arealways so certain of themselves, but wiser people so full ofdoubts." -- Bertrand RussellVery helpful and informative. Thanks, Rudy.SteveT 这篇关于比较两个可能溢出的倍数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！