大数如何除法？
我有一个大数字（整数，无符号）存储在两个变量中（如您所见，数字的高部分和低部分）：
unsigned long long int high;
unsigned long long int low;
我知道如何添加或减去其他某种变量。
但我需要除掉那种数字。 怎么做？ 我知道，我可以减去N次，但是，也许，还有更多更好的解决方案。 ;-)
语言：C
I have a big number (integer, unsigned) stored in 2 variables (as you can see, the high and low part of number):
unsigned long long int high;
unsigned long long int low;
I know how to add or subtract some other that-kind of variable.
But I need to divide that-kind of numbers. How to do it? I know, I can subtract N times, but, maybe, there are more better solutions. ;-)
Language: C
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
是的。 它将涉及轮班，我不建议在 C 中这样做。这是汇编程序仍然可以证明其价值的罕见例子之一，可以轻松地使运行速度快数百倍（而且我不认为我夸大了这个。）
我并不声称完全正确，但以下内容应该可以帮助您：
（1）将结果初始化为零。
(2) 将除数尽可能多地左移，但不能大于被除数。
(3) 从被除数中减去移位除数，结果加一。
(4) 现在将除数右移，直到再次小于剩余的被除数，并且每右移一次，结果左移一位。 除非满足停止条件，否则返回(3)。 （停止条件必须是“除数已为零”之类的东西，但我对此不确定。）
回到一些真正的编程问题真的感觉很棒:-)
Yes. It will involve shifts, and I don't recommend doing that in C. This is one of those rare examples where assembler can still prove its value, easily making things run hundreds of times faster (And I don't think I'm exaggerating this.)
I don't claim total correctness, but the following should get you going :
(1) Initialize result to zero.
(2) Shift divisor as many bits as possible to the left, without letting it become greater than the dividend.
(3) Subtract shifted divisor from dividend and add one to result.
(4) Now shift divisor to the right until once again, it is less than the remaining dividend, and for each right-shift, left-shift result by one bit. Go back to (3) unless stopping condition is satisfied. (Stopping condition must be something like "divisor has become zero", but I'm not certain about that.)
It really feels great to get back to some REAL programming problems :-)
您是否查看过任何大型库，例如 GNU MP BigNum？
Have you looked at any large-number libraries, such as GNU MP BigNum?
当N很大时，减去N次可能会很慢。
更好（即更复杂但更快）是移位和减法，使用您学到的算法 long小学里的小数除法。
[也可能有针对此类数字的第三方库和/或编译器特定的支持。]
Subtracting N times may be slow when N is large.
Better (i.e. more complicated but faster) would be shift-and-subtract, using the algorithm you learned to do long division of decimal numbers in elementary school.
[There may also be 3rd-party library and/or compiler-specific support for such numbers.]
唔。 我想如果你在“高”中有一些余量，你可以将其全部上移一位数，将高除以数字，然后将余数添加到低的剩余数字中，然后将低除以数字，然后将所有内容移回原处。
Hmm. I suppose if you have some headroom in "high", you could shift it all up one digit, divide high by the number, then add the remainder to the top remaining digit in low and divide low by the number, then shift everything back.
这是另一个执行 128 位算术的库。 GnuCash：Math128。
Here's another library doing 128 bit arithmetic. GnuCash: Math128.
根据我下面的评论者，我之前的回答很愚蠢。
很快，我的新答案是，当我过去尝试这样做时，它几乎总是涉及移位，因为它是唯一可以跨多个“单词”应用的操作，如果你愿意的话，并且让它看起来像与一个大字相同（除了必须跟踪结转位）。
有几种不同的方法，但我不知道有什么比使用班次更好的一般方向，除非您的硬件有一些特殊的操作。
Per my commenters below, my previous answer was stupid.
Quickly, my new answer would be that when I've tried to do this in the past, it almost always involved shifting, because it's the only operation that can be applied across multiple "words", if you will, and have it look the same as if it were one large word (with the exception of having to track carryover bits).
There are a couple different approaches to it, but I don't know of any better general direction than using shifts, unless your hardware has some special operations.
您可以实现“BigInt”类型算法来对字符串数组进行除法。 为每个高、低对创建 1 个字符串数组并进行除法。 将结果存储在另一个字符串数组中，然后转换回高、低整数对。
由于语言是 C，因此该数组可能是字符数组。 将其视为类似于我上面提到的“字符串数组”。
You could implement a "BigInt" type algorithm that does divisions on string arrays. Create 1 string array for each high,low pair and do the division. Store the result in another string array, then convert back to high,low integer pair.
Since the language is C, the array would probably be a character array. Consider it analogous to the "string array" I was mentioning above.
您可以使用汇编器循环和“带进位的加/减（adc/sbb）”指令对任意大的二进制对象进行加法和减法。 您可以使用它们来实现其他操作。 我个人从未研究过做除这两件事之外的任何事情。
You can do addition and subtraction of arbitrarily large binary objects using the assembler looping and "add/subtract with carry (adc/sbb)" instructions. You can implement the other operations using them. I've never investigated doing anything beyond those two personally.
如果您的处理器（或 C 库）具有快速 64 位除法，您可以将 128 位除法分解为多个部分（与在具有 16 位除法的处理器上执行 32 位除法的方式相同）。
顺便说一句，如果您知道被除数和除数的典型值是什么，则可以使用各种技巧。 这些数字的来源是什么？ 如果你的很多案件都可以很快得到解决，那么偶尔的案件需要很长时间也没关系。
另外，如果你能找到近似答案可以的情况，那就为许多快速近似打开了大门。
If your processor (or your C library) has a fast 64-bit divide, you can break the 128-bit divide into pieces (the same way you'd do a 32-bit divide on processors that had 16-bit divisions).
By the way, there are all sorts of tricks you can use if you know what typical values will be for the dividend and divisor. What is the source of these numbers? If a lot of your cases can be solved quickly, it might be OK the occasional case takes a long time.
Also, if you can find cases where an approximate answer is OK, that opens the door to a lot of speedy approximations.