整数除法运算装置及整数除法运算方法

摘要

本发明的装置用整数除数除整数被除数、产生整数商。该装置将除数右端位与被除数的M位对齐，对该被除数和除数进行对位处理。从被除数的各个位中选定看来应该与除数对齐的位的整数值和上述除数进行比较。根据该比较结果，将与被除数的M位及其左侧的位相对应的商数位设为0。根据上述比较结果、在上述对位状态下，通过被除数除以除数，算出在未设定为0的商数位中的商位值。

说明书

本发明涉及计算机系统中进行除法运算用的装置及方法。

大多数计算机系统都有整数除法运算装置，即整数被除数除以整数除数的运算装置。原有的整数除法运算装置都是对被除数及除数返复进行移位及减法处理。原有的这种整数除法运算装置已经多次公开发表。例如，在约翰·埃尔·赫奈西(ジョン·ェル·ヘネツ-)和戴维特·埃·帕达松(デビツド.エ-パタ-ソン)合著的“计算机功能结构、定量方法”(1990年，美国加利福尼亚州圣马特奥，莫尔干考夫曼(モルガンカウフマン)公司出版)中就有阐述。本说明书参考了其中的阐述内容。

移位及减法处理都要花费时间和运算费用。原有的整数除法装置由于反复对被除数及除数进行移位和减法运算，由于运算所花费的时间，增大了运算费用。

因此要求提供一种更有效的除法运算装置及除法运算方法。

为了解决上述课题，本发明提供一种进行整数被除数除以整数除数的运算，生成整数商用的装置及方法。本发明的装置是在将除数的右端位与被除数的M位对位以后进行的除法运算。M是表示被除数的位的位置上正整数值。从被除数的各个位中选定看来应该是与除数位对位的位的整数值同除数进行比较。

根据该比较的结果，将与被除数的M位和位于其左侧的被除数位相对应的位置处的商数位设为0。再根据上述比较结果，在经过上述对位处理的状态下，进行被除数除以除数的除法运算，算出未设定为0的商数位的值。

图1是表示以本发明的实施例为根据的整数除法装置的运作的流程图。

图2A—2C是以本发明的实施例为根据的整数除法运算处理的示例图。    

图3是表示根据本发明的实施例，将除数和被除数对位，进行处理的流程图。    

图4A—4L是表示以本发明的实施例为根据的整数除法运算处理的另一示例图。

图5是整数除法的示意图。

图6是以本发明的第1实施例为根据的整数除法运算装置的框图。

图7是以本发明的第2实施例为根据的整数除法运算装置的框图。

图8是以本发明的第3实施例为根据的整数除法运算装置的框图。

下面参照附图详细说明本发明的特征和优点、以及各实施例的结构和运作。附图中，同一标号表示相同的或类似的部件。

本发明的整数除法运算装置与原有的整数除法运算装置及方法相比较，其运算时间短，运算费用低。特别是在整数除法运算中，当商位短时，即与商数的全部位数相对应的设在商数开头的0的位数多时，或被除数的位数短时，本发明的有效性显著。本发明能应用于需用整数除法的一切数据处理装置。例如，本发明能应用于RISC(限定命令置位计算机)。在ジ-ケ·ケィソ和ジェィ·ハィンリツヒ合著的“MIPSRISC功能结构”(1992年，美国新泽西州英格尔伍德，プレンティスホ-ル公司出版)；マィク·ヅョンソソ著的超标量微处理机结构(1991年，プレンティスホ-ル公司出版)，以及ステフアン·ビ-·フア-バ-著的VLSIRISC功能结构(1989年，美国纽约州纽约，マ-セルデツカ-公司出版)等中都有关于RISC的说明。本说明书参考了这些说明。

本发明的整数除法运算装置能进行带符号的整数除法运算和不带符号的整数除法运算。为了便于说明，本说明书首先说明不带符号的整数除法运算。然后再讨论带符号的整数除法运算。

在详细说明本发明之前，先说明原有的整数除法运算装置如何运算，例如怎样进行9÷3的运算。在许多文献中都对原有的整数除法运算装置发表过阐述。例如有上述的赫奈西和帕达松所著的“计算机功能结构定量方法。图4A表示在9÷3的运算中，被除数9和除数3＝值的表示方法。被除数的各位用DD0—DD7表示。DD0是右端位即最低位，DD7是左端位即最高位。除数的各位用DS0—DS7表示。DS0是右端位。DS7是左端位。商数的各位用Q0—Q7表示。Q0是右端位，Q7是左端位。图5示出了这些位。

如图4B所示，原有的整数除法运算装置将除数的右端位DS0与被除数的左端位DD7对齐。然后，从被除数中与除数对齐的位(在图4B的情况下，是位DD7)相对应的整数值中减去除数。即从与被除数位DD7相对应的整数值0中减去除数3，得-3。因减得的结果为负，所以将商数位Q7设定为0。如果减得的结果为正(包括0)，则商位Q7设定为1。在图4B的情况下，商位Q7设定为0。

其次，如图4C所示，将除数向右移1位。从与除数对齐的被除数位(在图4C中，位DD7及DD6)相对应的右端一侧的位中所有的整数值中减去除数。即从与被除数位DD7及DD6相对应的右端一例的位中所有的整数值0中减去除数3，得-3。由于减得的结果为负，所以设定商数位Q6为0。如果减得的结果为正，则商位Q6设定为1。在图4C中，商数位Q6设定为0。

这样，如图4D—4G所示，商数位Q5—Q2也设定为0。

设定商数位Q2为0后，如图4H所示，将除数向右移1位，从与除数对齐的被除数位(图4H中，位DD7—DD1)相对应的右端一侧的位中所有的整数值中减去除数。即从与被除数位DD7—DD1相对应的右端一侧的位中所有的整数值4中减去除数3，得1。因减得的结果为正，所以设定商数位Q1为1。这时，如图4I所示，根据该减法运算结果修正被除数。

其次，如图4I所示，将除数向右移1位，从与除数对齐的被除数位(图4I中，位DD7—DD0)相对应的右端一侧位中所有的整数值中减去除数。即从与被除数DD7—DD0相对应的右端一侧位中所有的整数值3中减去除数3，得0。因减得的结果为正，所以设定商数位Q0为1。这时，由于除数的右端位DS0与被除数的右端位DD0对齐，所以整数除法运算结束。

至此应该注意的是，在原有的整数除法装置的运算中，与被除数起始的各0位相对应的商数位总为0。这在无符号整数除法运算中总是正确的。这是因为从0中减去非零的除数所致。

因此，正如本发明者们所发现的那样，如果将与被除数起始一侧的各0位相对应位置的商数位设定为0，然后将除数的右端位DS0与被除数起始的非零位即被除数左端一侧开始为1的位对齐，开始进行原有的整数除法运算，则可省去许多移位过程和减法运算过程。

这样，如果能省去移位及减法过程，则可缩短整数除法处理的时间，减少运算费用。实际上能缩短的时间或能节约的费用的多少都取决于被除数、除数及商值。通常，如果商数位短，即如果与商数的全部位数相对应的起始的0数多，或者如果被除数短，则能提高整数除法运算装置的性能。

本发明的第1个实施例进行整数除法运算时，对被除数从左向右搜索，具体确定最初的非零被除数位的位置，即起始非零被除数位的位置。然后将除数的右端位DS0与该起始非零被除数位对齐。而且将与该起始非零被除数位的左侧的被除数位相对应的商数位设为0。这样，将被除数和除数对齐，并将适当个数的0设定为商数后，开始进行用图4A—4I说明过的原有的整数除法处理。

图4J表示本发明的第1个实施例的运作。图中，起始非零被除数位为DD3。将除数的右端位DS0与该被除数位DD3对齐，将与起始非零被除数位DD3的左侧的被除数位DD7—DD4相对应的商数位Q7—Q4设为0。

图6是以本发明的第1个实施例为根据的整数除法运算装置602的框图。整数除法运算装置602备有被除数寄存器604和除数寄存器606。    

起始非零位探试电路(FFO)608将寄存器604中的被除数的各位从左向右调，具体确定起始非零被除数位的位置W。检索的位的位置W提供给控制状态装置610。在图4J中，位的位置W为3。

控制状态装置610将指示送给1—63位右移位寄存器612，将被除数的W位向右进行逻辑移位。该寄存器612能将1—63任意位数的目标数据向右移位。这时，各0移向寄存器612的左端。向右移位后的被除数根据控制状态装置610的指示，通过多路转换器616及620，存储在寄存器604中。

移出右移位寄存器612以外的被除数位存储在暂存寄存器(图中未示出)中。该暂存寄存器分别与右移位寄存器612、左移位寄存器614及左移位寄存器622连接。在图4J中，该暂存寄存器所存的为“001”。

控制状态装置610将与被除数位W的左侧的被除数位相对应的商数位设定为0。这些商数位最好存储在寄存器(图中未示出)中。在图4J中，将商数位Q7—Q4设定为0。

这样将除数和被除数对齐，并将适当个数的起始商数位设定为0，并将其存入寄存器中，然后利用图6所示的各部件开始进行原有的整数除法运算。

即减法器618从寄存器604中的被除数中减去寄存器606中的除数。在图4J所示例中，从1减去3。控制状态装置610断定减得结果为负时，将商数位Q3设定为0，将指示送给左移位寄存器614，将寄存器604中的被除数向左移一位。这时，暂存寄存器内的左端位被移到左移位寄存器614的右端位置。该左移位后的被除数值通过多路转换器616及620，存入寄存器604。在图4J中，将二进制数字“10”存入寄存器604。

控制状态装置610反复进行上述处理，设商数位Q2为0，将二进制数字“100”存入寄存器604。

根据控制状态装置610的指示反复进行同样的处理，在图4J的情况下，用减法器618从寄存器604中现在的被除数中减去寄存器606中的除数后的值为正1。即4－3＝1。因此，控制状态装置610设定商数位Q1为1，指示左移位寄存器622，将减法器618的输出数据向左移1位。而且将存储在暂存寄存器中的值的左端位移到该左移后的输出数据的右端位置。该左移后的输出数据成为现在的被除数，通过多路转换器616及620，存入寄存器604中。在图4J所示例中，将二进制数字“11”存入寄存器604。

根据控制状态装置610的指令，再反复进行上述处理。即在减法器618中，从存储在寄存器604中的现在的被除数中减去存储在寄存器606中的除数。因减法器输出0，所以控制状态装置610设定商位Q0为1。至此，整数除法运算结束。

图6中的整数除法装置602的控制状态装置610最好用硬件实现。或者采用根据计算机的软件运作的处理机也可。起始非零探试电路(FFO)608可应用浮点加法器的正规化控制来实现。其结构及运作，通过参照本说明书，本专业的技术人员自会明白。图6中的其它部件是专业的技术人员已知的。

现说明本发明的第2个实施例。该实施例在进行整数除法运算时，将被除数从左向右调动，具体确定最初的非零位、即起始非零被除数位的位置。然后将除数从左向右调动，确定最初的非零位即起始非零除数位的具体位置。从起始非零被除数位的位置减去起始非零除数位的位置，生成两者对齐的位的位置。

与该对位的位置相对应的被除数位，简称为对位被除数位，将除数的右端位DS0与该经过对位处理的被除数位对齐。然后将与该对位被除数位和其左侧的被除数位相对应的商数位设为0。这样将除数和被除数进行对位处理，在商数的开头设定适当个数的0后，开始进行参照图4A—4I说明过的原有的整数除法运算。

图4L表示本发明的第2个实施例的运作。该图中，起始非零被除数位为DD3。起始非零除数位为DS1。因此对位的位置为2。因此，将除数的右端位DS0与被除数位DD2对齐，将与被除数位DD2和其左侧的被除数位DD7—DD3相对应的商数位Q2及Q7—Q3设为0。    

第2个实施例根据起始非零被除数位的位置和起始非零除数位的位置，将除数与被除数的对位处理达到最佳位置。

图7是以本发明的第2个实施例为根据的整数除法运算装置702的框图。整数除法运算装置702备有被除数寄存器704和除数寄存器706。

起始非零探试电路(FFO)708将寄存器704中的被除数从左向右调动，具体确定起始非零被除数位的位置X，将该位置X输送至减法器712。在图4L所示例中，X＝3。

起始非零探试电路(FFO)710将寄存器706中的除数从左向右调动，具体确定起始非零除数位的位置Y，将该位置Y输送至减法器712。在图4L所示例中，Y＝1。

减法器712从X中减去Y，生成上述对位位的位置。在图4L所示例中，该对位位置为2。该对位位置被输至控制状态装置714。

控制状态装置714向1—63位右移位寄存器716发送指示，指令将被除数右移进行与对位位置相对应位数的逻辑移位。根据控制状态装置714的指示，右移后的被除数通过多路转换器720及726，存入寄存器704。

移出右移位寄存器716以外的被除数位存入暂存寄存器中(图中未示出)。该暂存寄存器分别与右移位寄存器716、左移位寄存器718和左移位寄存器724连接。在图4L中，该暂存寄存器所存的为“01”。    

控制状态装置714将比对位位置高的商数位设定为0。这些商数位存入寄存器中即可(图中未示出)。在图4L中，设定商数位Q7—Q2为0。

对除数和被除数进行对位处理，将从开头算起的适当个数的商数位设定为0，并存入寄存器。然后利用图7所示的各部件，开始进行原有的整数除法运算。该整数除法运算方法与参照图6说明过的相同，所以不再重复说明。

图7中的整数除法运算装置702的控制状态装置714最好用硬件实现。或者也可采用根据计算机软件运作的处理机。起始非零探试电路(FFO)708及710可应用浮点加法器的正规化控制来实现。其结构及运作，通过参照本说明书，本专业的技术人员会明白的。图7中的其它部件是本专业工作者已知的。

现说明本发明的第3个实施例。该实施例将除数右端位DS0与被除数的规定位对齐。然后从被除数中与除数对齐的位相对应的整数值中减去除数。

如果减得的结果为负，则将上述规定的与被除数位和其左侧的被除数位相对应的商位设定为0，对经过对位运算的被除数及除数进行原有的整数除法运算。如果减得结果为正(包括0)，则对被除数和未经过对位运算的除数进行原有的整数除法运算。下面详细说明本发明的第3个实施例。

图4K表示本发明的第3个实施例的运作。该图中，DD4是被除数的规定位。将除数的右端位DS0与该被除数位DD4对齐。将与规定的被除数位DD4和其左侧的被除数位DD7—DD5相对应的商数位Q4及Q7—Q5设为0。

图1是表示本发明的第3个实施例的运作的流程图。参照该流程图和图2A—2C中的除法例，详细说明本发明的第3个实施例。在图示例中使用16位被除数202和16位除数204。在本发明中，被除数，除数及商数最好为同一位长。图1中的流程图从步102开始。

在步104中，将除数204的右端位DS0与被除数202的第1规定被除数位M对齐。即通过将被除数位M与除数位DS0对齐，将被除数和除数进行对位处理。M是预先决定的值。在图2A—2C中，M为4。因此如图2B所示，除数204的位DS0与被除数202的位DD4对位。

再在步104中，从表示被除数202的位中与除数204对位的位(图2B中DD15—DD4)的整数值中减去除数204。在图2B中，得32－4＝28。

在步106中，判定步104中减得的结果是否为负。即在步106中判断如下的关系是否正确。

2的M次方*除数＞被除数式中符号*表示乘号。

在图2A—2C所示例中，步104中的减得结果不为负，即上述关系不正确。因此执行步112以后的一系列处理。如果步104中减得的结果为负，即如果上述关系正确，则执行步108以后的一系列处理。

在步108中，在商数的开头部分插入“K—M”个数的0，将该商数存入寄存器中。在本实施例中，K是被除数202的位数，与除数204或商的位数相等。于是，将与第1规定的被除数位DD4和其左侧的被除数位DD15—DD5相对应的商数位设为0。

步108结束后，参照图4A—4I说明的原有的整数除法的第1阶段也就结束。即将除数的右端位DS0与第1规定的被除数位DD4对位进行的除法的第1阶段结束。就是说对与第1规定的被除数位DD4相对应的商数位Q4设定数值。另外，也可以采用其它众所周知的整数除法运算方法代替图4A—4I中的方法。在步110中，继续进行参照图4A一4I说明的原有的整数除法运算，在步108中生成未设定为0的商数位。在步110中利用众所周知的方法生成余数。经过步110以后，在步122中除法运算结束。

当在步106判定步104中减得的结果不为负时，执行步112以后的一系列处理。

步112将除数204的右端位DS0与被除数202的第2规定被除数位N对位。N是预先确定的规定正整数。在图2A—2C所示例中，N＝8。因此，如图2C所示，除数204的右端位DS0与被除数204的位DD8对位。然后，从被除数202的位中表示与除数204对位的位(在本例的情况下，为DD15—DD8)的整数值中减去除数204。在图2C的情况下为2－4＝-2。

步114判断步112中减得的结果是否为负。如果不为负，执行步120以后的处理。如图2C所示；如果为负，则执行步116以后的一系列处理。

在步116中，在商数的开头端插入“K—N”个0。这样将与第2规定的被除数位DD8和其左侧的被除数位DD15—DD9相对应的商数位设为0。

步116结束后，参照图4A—4I说明的原有的整数除法的第1阶段也就结束。即将除数204的右端位DS0与第2规定被除数位DD8对齐进行的除法的第1阶段结束。就是说将与第2规定的被除数位DD8相对应的商数位Q8设定数值。另外，也可以采用其它已知的整数除法运算方法代替图4A—4I中的方法。在步118中，继续进行参照图4A—4I说明的原有的整数除法运算，在步116中生成未设定0的商数位。步118利用众所周知的方法生成余数。经过步118以后，在步122中除法运算结束。

当在步114中判定步112中减得的结果不为负后，执行步120以后的处理。

步120开始进行上述原有的整数除法处理或众所周知的其它除法处理。即将除数204的右端位DS0与被除数202的左端位“K—1”对齐后，生成全部商数位。这时，商数中连一个0也不作预设定。另外，除数204也不与被除数202的位对位。即，直接执行原有的整数除法运算。步120利用众所周知的方法生成余数。经过步120以后，在步122中除法运算结束。

本发明的第3实施例在整数除法运算中试行两次最佳化处理。第1次最佳化处理与步104、106、108及110相对应，将除数204的右端位与被除数202的M位对齐。第2次最佳化处理与步112、114、116及118相对应，将除数204的右端位与被除数202的N位对位。在本发明中，由于在整数除法运算中进行最佳化处理，所以只进行一次最佳化即可。或者也可以试行3次以上的最佳化处理。随着最佳化处理次数的重复，作为与除数右端位对位的目标规定的被除数位的位置增多。这种变更形态，本专业工作者是会明白的。

可使用各种数字，例如K＝64、M＝16、N＝32。K、M、N的值也取永久的设定值，也可使用适当的软件命令，由程序进行调整。

图3是表示图1中的步104的详细过程的流程图。该流程从步302开始，直接移到步304。

在步304中，将被除数向右移M位。这时，各0移到被除数的左端位的位置。将其称为逻辑右移值。    

在步306中，从右移位后的被除数中减去除数。

图1中的步112与步104相同，但可说明将步304中的M置换成N。步104及步112中的其它运作，本专业工作者是会明白的。

图8是以本发明的第3个实施例为根据的整数除法运算装置802的框图。该整数除法运算装置802备有被除数寄存器804和除数寄存器806。

控制状态装置814将指示发送至右移位寄存器808，将寄存器804中的被除数向右进行M位逻辑移位。最好使M＝16，但也可是其它数。根据控制状态装置814的指示，右移位后的被除数通过多路转换器812及820，存入寄存器804。移出右移位寄存器808以外的被除数位存入暂存寄存器中(图中未示出)。该暂存寄存器分别与右移位寄存器808，左移位寄存器810及左移位寄存器818连接。在图4K中，M为4，该暂存寄存器中所存由为“1001”。

控制状态装置814将指示发送至减法器816，从寄存器804中的被除数中减去寄存器806中的除数，并接收减得的结果。如果减得的结果为负，控制状态装置814将寄存器中存储的商数位中位置在M以上的商数位设为0。在图4K所示例中，将商数位Q7—Q4设为0。        

经过对除数和被除数进行对位处理后，在商数位的开头设定适当个数的0，并存入寄存器。然后利用图8所示的各部件，开始进行原有的整数除法运算。该整数除法与参照图6说明过的相同，其重复说明从略。

当减法器816减得的结果为正时，控制状态装置814指示右移位寄存器808，再将寄存器804中的被除数向右移M位，将被除数从原来的位置向右共计移N位(N＝M＋M)。根据控制状态装置814的指示，向右移位后的被除数通过多路转换器812及820，存入寄存器604。移出左移位寄存器808以外的被除数位存入暂存寄存器中作为右移位。

控制状态装置814指示减法器816，从寄存器804中的被除数的现在值减去寄存器806中的除数，并接收减得的结果。如果减得的结果为负，控制状态装置814将寄存器中存储的商数位中位于N以上的商数位设定为0。

经过对除数和被除数进行对位处理后，在商数位的开头设定适当个数的0，并存入寄存器中。然后使用图8所示的各部件，开始进行原有的整数除法运算。该整数除法与参照图6说明过的相同，因此其重复说明从略。    

如果上述第2次减得的结果为正，控制状态装置814再将原被除数存入寄存器804。然后利用图8所示的各部件，开始进行原有的整数除法运算。这时，除数的右端位与被除数的左端位对位。

图8中的整数除法运算装置802的控制状态装置814最好用硬件实现。或者也可以采用根据计算机软件运作的处理机来实现。图8中的其它部件是本专业工作者已知的。

以本发明为根据的整数除法运算装置，已说明了有关无符号整数除法运算。将本发明的第1—第3实施例经过稍加变更之后，就能进行带符号的整数除法运算。

例如，在本发明的任意一个实施例中都可增加第1电路。该第1电路是在进行前面说明过的整数除法的算法之前产生被除数及除数两者的绝对值的电路。另外，再增加第2电路。该第2电路是根据被除数和除数的符号调整商数符号的电路。例如，如果被除数和除数都为正或都为负，则设定商的符号为正。在进行绝对值运算之前进行该符号的设定。

对于实现该第1及第2电路的方法，本专业技术人员都很清楚。为了实现带符号的整数除法运算，在本发明的整数除法运算装置中也可进行其它形态的变更，参照本说明书，本专业工作者能明白这种变更形态。

以第2实施例为根据的整数除法装置的运算速度，通常比以第3实施例为根据的装置快。其原因有二，其一是在第2实施例对除数和被除数进行对位处理，找出最适合的对位的位置。然而第3实施例是将除数和被除数的对位选定在任意的位置上。其二是第2实施例预先确定除数的对位位置，不需要反复进行移位及减法运算。

可是在第3实施例中的整数除法运算装置中所需要的硬件比第2个实施例中的少。其原因有三，其一是第3实施例完全不需要右移位处理器。即第3实施例不需要进行1—”K—1”(K为除数的长度)的任意位数的移位的右移位处理器。其二是第3实施例不需要上述的两个起始非零探试电路(FFO)。其三是第3实施例与第2实施例相比较，前者不需要复杂的状态装置。

第1实施例中的整数除法运算装置则是将第2及第3实施例的优点及缺点折中的一种装置。可是，对于具有这种一般性特征的实施例来说，本发明的实施并不一定正确。

在全部除法运算阶段中原有的非复原除法运算程序都能适用。

在以上对于各实施例所作的说明，都是展示在开始进行原有的除法运算之前，为了与被除数对位在确定除数需要前移的范围的过程中所用的各种不同的程序和技术。

上述各实施例只是本发明的几个示例，本发明并不受此限，即本发明的范围不受上述实施例的限制，而由权利要求范围所规定。