分裂问题 [英] division problem
问题描述
假设unsigned int（32位）是计算机可以用单个变量代表
的最大数字。
现在，我有一个大整数（小于64位，但大于32位）。
i用这种方式表示：
unsigned int dividend [2]：
divident [0]存储低32位大整数，被分红[1]存储高32
位大整数。
我的问题是怎么做一个除法，比如这个
商=大整数/除数，余数=大整数mod除数
（除数是32位无符号整数）;
我如何获得商数和余数？
感谢您的帮助！
Supposed unsigned int(32 bits) is the largest number that computer can
represent with a single variable.
Now, i have a big integer ( less than 64 bit, but great than 32 bit) .
i represent it by this way:
unsigned int dividend[2] :
divident[0] store low 32 bits of big integer, dividend[1] store high 32
bits of big integer.
my problem is how make a division, like this
quotient = big integer/ divisor, remainder = big integer mod divisor
(divisor is 32 bit unsigned integer);
how can i get quotient, and remainder ?
thanks your help!
推荐答案
" ja ******** @ gmail.com" < ja ******** @ gmail.comwrote：
"ja********@gmail.com" <ja********@gmail.comwrote:
假设unsigned int（32位）是计算机可以使用的最大数字
表示单个变量。
现在，我有一个大整数（小于64位，但大于32位）。
i用这种方式表示：
unsigned int dividend [2]：
divident [0]存储低32位的大整数，dividend [1]商店高32
位大整数。
我的问题是怎么做分工，比如这个
商=大整数/除数，余数=大整数mod除数
（除数是32位无符号整数）;
我怎样才能得到商和余数？
Supposed unsigned int(32 bits) is the largest number that computer can
represent with a single variable.
Now, i have a big integer ( less than 64 bit, but great than 32 bit) .
i represent it by this way:
unsigned int dividend[2] :
divident[0] store low 32 bits of big integer, dividend[1] store high 32
bits of big integer.
my problem is how make a division, like this
quotient = big integer/ divisor, remainder = big integer mod divisor
(divisor is 32 bit unsigned integer);
how can i get quotient, and remainder ?
长师。
HTH;手; DYODH。
Richard
Long division.
HTH; HAND; DYODH.
Richard
ja ******** @ gmail.com 说：
假设unsigned int（32位）是计算机中最大的数字可以
表示单个变量。
现在，我有一个大整数（小于64位，但大于32位）。
i用这种方式代表它：
unsigned int dividend [2]：
divident [0]存储低32位的大整数，红利[1]商店高32
位大整数。
我的问题是如何制作一个师，像这样
商=大整数/除数，余数=大整数mod除数
（除数是32位无符号整数）;
我怎样才能得到商，余数？
Supposed unsigned int(32 bits) is the largest number that computer can
represent with a single variable.
Now, i have a big integer ( less than 64 bit, but great than 32 bit) .
i represent it by this way:
unsigned int dividend[2] :
divident[0] store low 32 bits of big integer, dividend[1] store high 32
bits of big integer.
my problem is how make a division, like this
quotient = big integer/ divisor, remainder = big integer mod divisor
(divisor is 32 bit unsigned integer);
how can i get quotient, and remainder ?
让大号为N：
11001110100111111001101001001010111010110101101010 11010110101010
让除数为D：
10111011101100111101010101010101
设S0为N的最高位与整个D的差值。
问：1
------------------------------ -------------------------------------
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
-------------------------------- ---
S0：00010010111010111100010011110101
从N获得下一位：
Q：10
-------------------------------------------- -----------------------
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
--------- --------------------------
00100101110101111000100111101011
D：10111011101100111101010101010101
从N获得下一位：
Q：100
------------ -------------------------------------------------- -----
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
-------------- ---------------------
01001011101011110001001111010111
D：10111011101100111101010101010101
从N获得下一位：
Q：1000
----------------- --------------------------------------------------
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
------------------- ----------------
10010111010111100010011110101111
D：10111011101100111101 010101010101
从N获取下一位：
Q：10001
------- -------------------------------------------------- ----------
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
--------- --------------------------
100101110101111000100111101011110
D：10111011101100111101010101010101
-------------------------------
S1：1110011000010000111101000001000
从N获得下一位：
Q：100011
------------ -------------------------------------------------- -----
N：11001110100111111001101001001010111010110101101010 11010110101010
D：10111011101100111101010101010101
-------------- ---------------------
100101110101111000100111101011110
D：10111011101100111101010 101010101
-------------------------------
11100110000100001111010000010001
D：10111011101100111101010101010101
等等（我可能已经把一些比特混淆了因为我做了这个
by但是你会自动这样做。）
当你用完了比特，Q就是你的商，剩下的就是，
奇怪的是，你的剩余部分。
除了你的
程序只需要知道你的1-时间表。要么D大于你当前正在比较的
位组（在这种情况下Q位是0），
或者它不是（在这种情况下，Q位为1）。减去并继续前进。
-
Richard Heathfield
Usenet是一个奇怪的地方 - dmr 29/7/1999
http://www.cpax.org.uk
电子邮件：rjh在上述域名中， - www。
Let the big number be N:
11001110100111111001101001001010111010110101101010 11010110101010
Let the divisor be D:
10111011101100111101010101010101
Let S0 be the difference between the top bits of N and the whole of D.
Q: 1
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
S0:00010010111010111100010011110101
Get the next bit from N:
Q: 10
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
00100101110101111000100111101011
D: 10111011101100111101010101010101
Get the next bit from N:
Q: 100
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
01001011101011110001001111010111
D: 10111011101100111101010101010101
Get the next bit from N:
Q: 1000
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
10010111010111100010011110101111
D: 10111011101100111101010101010101
Get the next bit from N:
Q: 10001
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
100101110101111000100111101011110
D: 10111011101100111101010101010101
-------------------------------
S1: 1110011000010000111101000001000
Get the next bit from N:
Q: 100011
-------------------------------------------------------------------
N: 11001110100111111001101001001010111010110101101010 11010110101010
D: 10111011101100111101010101010101
-----------------------------------
100101110101111000100111101011110
D: 10111011101100111101010101010101
-------------------------------
11100110000100001111010000010001
D: 10111011101100111101010101010101
etc etc etc. (I might have got some of the bits mixed up because I did this
by hand, but you''ll be doing this automatically.)
When you run out of bits, Q is your quotient and whatever is left over is,
strangely enough, your remainder.
Division is much simpler in binary than in any other number base, since your
program only has to know your 1-times table. Either D is greater than the
set of bits you''re currently comparing with (in which case the Q-bit is 0),
or it isn''t (in which case the Q-bit is 1). Subtract and move on.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
< ja ******** @ gmail.com写信息
新闻：11 ********************** @ i12g2000cwa.googlegr oups.com ...
<ja********@gmail.comwrote in message
news:11**********************@i12g2000cwa.googlegr oups.com...
假设unsigned int（32位）是计算机可以用单个变量表示的最大数字
。
现在，我有一个大整数（小于64位，但大于32位）。
i用这种方式表示：
unsigned int dividend [2]：
divident [0]存储低32位的大整数，dividend [1]存储高32
位的大整数。
我的问题是怎么做分工，比如这个
商=大整数/除数，余数=大整数mod除数
（除数是32位无符号整数）;
我怎么能得到quotie恩特和其余的？
Supposed unsigned int(32 bits) is the largest number that computer can
represent with a single variable.
Now, i have a big integer ( less than 64 bit, but great than 32 bit) .
i represent it by this way:
unsigned int dividend[2] :
divident[0] store low 32 bits of big integer, dividend[1] store high 32
bits of big integer.
my problem is how make a division, like this
quotient = big integer/ divisor, remainder = big integer mod divisor
(divisor is 32 bit unsigned integer);
how can i get quotient, and remainder ?
Richard Heathfield建议进行位移，对于你的问题，这将是好的。然而，即使在你提出
的情况下，它[非常！]也不是最理想的。
关键问题 - 添加的情况也是如此，减法和
乘法 - 是处理器本身具有整数加法，
减法，乘法和除法指令;但是他们处理比你感兴趣的更小的操作数。
关键问题是是否可以使用这些小的操作数。说明
多次处理较大的操作数。
在加法和减法的情况下，答案显然是肯定的。即使
一个是在''C'编程并且没有直接访问处理器的CARRY位
，如果添加的结果是小于任何一个
输入参数（必须是无符号），然后发生进位。用了很少的思考，可以编写一个多精度整数加法，它不会对b $ b表现不好（尽管它不如汇编语言那么高效）例如：
unsigned int input1 [2]; / * LSI首先用于所有这些* /
unsigned int input2 [2];
unsigned int output [3]; / *结果有一个int保持执行。 * /
unsigned int carryout [1];
输出[0] = input1 [0] + input2 [0];
if（（output [0]< input1 [0]）||（output [0]< input2 [0]））
carryout [0] = 1;
else
carryout [0] = 0;
输出[1] = input1 [1] + input2 [1] ;
if（（输出[1]< input1 [1]）||（输出[1]< input2 [1]））
输出[2] = 1;
其他
输出[2] = 0;
/ *现在，处理进位超出LSI * /
if（carryout [0]）
{
输出[1] ++;
if（！output [1]）
输出[2] ++;
}
我不喜欢声称我在上面没有犯过某种错误（我从头开始做这件事）。最重要的是，人们可以相当有效地在''C'中减去大整数。$ / b
注意上面的解决方案使用的是使用本机机器指令添加处理器的内在能力
。
理查德希思菲尔德建议的解决方案和做好原因一样粗糙。 $ b一次加一点（与上面的技术相比）。
我不会进入乘法...但是有一种方法可以使用
处理器的乘法能力也是如此。如果你想到它，你会很快弄明白的。
最后，师......这是最难的案例。
如果你试图做代数并弄清楚你是否可以使用小代数机器
分区指令要完成一个更大的师，你会很快来到你不可能的结论。 （幸运的是，唐纳德克努特和他的同伴
比你或我更有经验。最终有一种方法可以做到这一点。）
这个过程非常类似于人们做长手分工的方式。在
longhand division中，人们一次估计一位数，然后乘以
减去，然后继续下一位数。偶尔，一个人猜错了，并且b $ b必须增加或减少商数并重新做这个数字。
在算法中，数字是指数字。是16-32位;并且估算的结果可能只需要在一个方向上减去2个计数（有一个简单的和/ b
便宜的修正程序）。
经典算法假设机器有一个除法指令
，它取一个bitsm的股息2w，除以它的比特数w，
并产生bitsize w和其余bitsize w的商，带有溢出的可能性（这是算法故意避免的）。
对于典型的桌面处理器，w是32位，因此在一台机器上，你可以执行64/32分区的
指令。但是，通常编译器将只允许你进行32/32分区，所以你必须使用w = 16并应用
标准算法。
该算法基本上每次产生16位结果
（相比于位移方法，每次1位）。
如果你可以访问机器的汇编语言，通常你可以
一次获得[至少] 32位。
标准整数除法算法在''C'中编码有点尴尬，但是当数据大小事先知道时（因为它们在你的情况下），它会得到 br />
不那么尴尬。
我不会在这里包含代码（需要太多考虑）。
以下是你应该查询的资源。
a）Knuth在他的经典作品的第2卷中介绍了这一点：
http://www.amazon.com/Art-Computer- P ... e = UTF8& s =书籍
b）GMP有一些部门代码，在事件中编译
汇编 - 语言不可用于特定处理器。这将使用
数字估计。我描述的技术。
c）此外，这个URL应该会有所帮助。它还引用了Knuth。
http://en.wikipedia.org /wiki/Arbitra...ion_arithmetic
希思菲尔德的建议会很好。但是，在一般情况下，你不想这样做。
戴夫。
Richard Heathfield suggested bit-shifting, and for your problem this will
work just fine. However, it is [very!] suboptimal, even in the case you
proposed.
The key issue -- and it is the same situation for addition, subtraction, and
multiplication -- is that the processor inherently has integer addition,
subtraction, multiplication and division instructions; but they handle
operands smaller than you are interested in.
The key question is whether it is possible to use these "small" instructions
multiple times to deal with larger operands.
In the case of addition and subtraction, the answer is clearly YES. Even if
one is programming in ''C'' and doesn''t have direct access to the CARRY bit of
the processor, if the result of an addition is smaller than either of the
input arguments (which must be unsigned), then a carry occurred. With a
little thought, one can code multi-precision integer addition that doesn''t
perform badly (although it won''t be as efficient as assembly-language).
For example:
unsigned int input1[2]; /* LSI first for all of these */
unsigned int input2[2];
unsigned int output[3]; /* Result has one more int to hold carry out. */
unsigned int carryout[1];
output[0] = input1[0] + input2[0];
if ((output[0] < input1[0]) || (output[0] < input2[0]))
carryout[0] = 1;
else
carryout[0] = 0;
output[1] = input1[1] + input2[1];
if ((output[1] < input1[1]) || (output[1] < input2[1]))
output[2] = 1;
else
output[2] = 0;
/* Now, process the carry out of the LSI */
if (carryout[0])
{
output[1] ++;
if (! output[1])
output[2] ++;
}
I don''t claim that I didn''t make some kind of mistake in the above (I''m
doing this from scratch). The bottom line is that one can do addition and
subtraction of large integers in ''C'' fairly effectively.
Note that the solution above uses the inherent ability of the processor to
add using native machine instructions.
The solution suggested by Richard Heathfield is just as crude as doing
addition one bit at a time (compared to the technique above).
I won''t get into multiplication ... but there is a way to do that using the
processor''s multiplication ability, too. You''ll figure it out quickly if
you think about it.
And finally, division ... which is the toughest case.
If you try to do the algebra and figure out if you can use "small" machine
division instructions to accomplish a larger division, you''ll rapidly come
to the conculsion that you can''t. (Fortunately, Donald Knuth and his peers
are just a bit more experienced than you or I. It ends up there is a way to
do it.)
The process is very similar to the way people do longhand division. In
longhand division, people estimate one digit at a time, then multiply and
subtract, then go on to the next digit. Occasionally, one guesses wrong and
has to increase or decrease the quotient digit and re-do that digit.
In the algorithm, a "digit" is 16-32 bits; and the result of estimation may
be off by as much as 2 counts in one direction only (there is a simple and
cheap correction procedure).
The classic algorithm assumes that the machine has a division instruction
that takes a dividend of bitsize 2w, divides it by a divisor of bitsize w,
and produces a quotient of bitsize w and a remainder of bitsize w, with the
possibility of overflow (which is deliberately avoided by the algorithm).
For a typical desktop processor, w is 32 bits, so that in one machine
instruction you can do a 64/32 division. However, typically compilers will
only allow you to do a 32/32 division, so you have to use w=16 and apply the
standard algorithm.
The algorithm essentially will produce 16 bits of the result at a time
(versus 1 bit at a time from the bit-shifting approach).
If you have access to the assembly-language of the machine, normally you can
get [at least] 32 bits at a time.
The standard integer division algorithm is a bit awkward to code in ''C'', but
when the data sizes are known in advance (as they are in your case), it gets
less awkward.
I won''t include the code here (too much thought would be required).
Here are the resources you should look up.
a)Knuth covers this in Volume 2 of his classic work:
http://www.amazon.com/Art-Computer-P...e=UTF8&s=books
b)The GMP has some division code that is compiled in the event
assembly-language isn''t available for the specific processor. This will use
the "digit estimation" technique I described.
c)Also, this URL should be helpful. It also cites Knuth.
http://en.wikipedia.org/wiki/Arbitra...ion_arithmetic
Heathfield''s suggestion will work just fine. However, in the general case,
you don''t want to do that.
Dave.
这篇关于分裂问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
