精华内容
下载资源
问答
  •   开始理顺被除数与除数之间的关系 :首先11比3大,结果至少是1(余数最小1), 然后我让3翻倍,就是6,发现11比3翻倍后还要大,那么结果就至少是2了(假定余数是2,因为除数变大了),那我让这个6再翻倍,得12,...

      举个例子:11 除以 3 。
      开始理顺被除数与除数之间的关系 :首先11比3大,结果至少是1(余数最小为1), 然后我让3翻倍,就是6,发现11比3翻倍后还要大,那么结果就至少是2了(假定余数是2,因为除数变大了),那我让这个6再翻倍,得12,11不比12大,吓死我了,差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数,这个数是多少呢?我让11减去刚才最后一次的结果6,剩下5,我们计算5是3的几倍,也就是除法,看,递归出现了(因为我们又需要开始计算被除数与除数之间的关系了)。说得很乱,不严谨,大家看个大概,然后自己在纸上画一画,或者直接看我代码就好啦!

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(dividend == 0) return 0;
            if(divisor == 1) return dividend;
            
            if(divisor == -1)//除数是负值,判断一下被除数,让其最好也变成负的,如此结果为正数
            {
                if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数,都是直接返回相反数就好啦
                return INT_MAX;// 是最小的那个,那就返回最大的整数啦
            }
            long a = dividend;
            long b = divisor;
            int sign = 1; //辅助判断条件
            
            if((a>0&&b<0) || (a<0&&b>0))
            {
                sign = -1;
            }
            a = a>0?a:-a;
            b = b>0?b:-b;
            
            long res = div(a,b);
            if(sign>0)
            {
            	return res>INT_MAX?INT_MAX:res;
            }
            else
            return -res;
        }
        
        int div(long a, long b)// 似乎精髓和难点就在于下面这几句,递归思想,不断调用自己本身
        {  
            if(a<b) return 0;
            long count = 1;//前面的理解中,只要被除数>除数,余数最小都是1,所以让count为1
            long tb = b; // 在后面的代码中不更新b
            while((tb+tb)<=a)
            {
                count = count + count; // 最小解翻倍
                tb = tb+tb; //(除数每次翻倍,加上自己的本身) 当前测试的值也翻倍
            }
            return count + div(a-tb,b);
        }
    };
    

    在这里插入图片描述

    展开全文
  • 一、乘法运算 在计算机中,乘法运算是一种很重要的运算,有的机器由硬件乘法器直接完成乘法运算,有的机器内没有乘法器,但可以按机器作乘法运算的方法,用软件编程实现。...可见,这里包含着乘数.

    目录

    一、乘法运算

    1、分析笔算乘法

    2、笔算乘法的改进

    3、原码一位乘法

    4、原码两位乘法

    5、补码一位乘法

    6、补码两位乘

    二、除法运算

    1.分析笔算除法

    2、原码除法

    (1)恢复余数法

    (2)加减交替法

    (3)原码加减交替法所需的硬件配置

    (4)原码加减交替除法控制流程

    3、补码除法

    (1)补码加减交替法运算规则

    (2)补码加减交替法所需的硬件配置

    (3)补码加减交替法的控制流程


    一、乘法运算

    在计算机中,乘法运算是一种很重要的运算,有的机器由硬件乘法器直接完成乘法运算,有的机器内没有乘法器,但可以按机器作乘法运算的方法,用软件编程实现。因此,学习乘法运算方法不仅有助于乘法器的设计,也有助于乘法编程。

    下面从分析笔算乘法入手,介绍机器中用到的几种乘法运算方法。

    1、分析笔算乘法

    设A=0.1101,B=0.1011,求A×B。

    笔算乘法时乘积的符号由两数符号心算而得:正正得正;其数值部分的运算如下:

    所以  A×B=+0.10001111

    可见,这里包含着被乘数4的多次左移,以及四个位积的相加运算。

    若计算机完全模仿笔算乘法步骤,将会有两大困难:

    • 其一,将四个位积一次相加,机器难以实现;
    • 其二,乘积位数增长了一倍,这将造成器材的浪费和运算时间的增加。

    为此,对笔算乘法做些改进。

    2、笔算乘法的改进

    将A•B =  A•0.1011

       = 0.1A+0.001•A+0.0001•A

       = 0.1A+0.00•A+0.001(A+0.1A)

       = 0.1A+0.01[0•A+0.1(A+0.1A)]

       = 0.1{A+0.1[0•A+0.1(A+0.1A)]}

       = 2^-1{A+2^-1 [0•A+2^-1 (A+2^-1A)]}

       = 2^-1{A+2^-1 [0•A+2^-1 (A+2^-1(A+0))]}

    由上式可见,两数相乘的过程,可视作加法和移位(乘2^-1相当于做一位右移)两种运算,这对计算机来说是非常容易实现的。

    从初始值为0开始,对上式作分步运算,则:

    • 第一步:被乘数加零                 A+0=0.1101+0.0000=0.1101
    • 第二步:右移一位,得新的部分积   2^-1 (A+0)=0.01101
    • 第三步:被乘数加部分积                       A+2^-1(A+0)=0.1101+0.01101=1.00111
    • 第四步:右移一位,得新的部分积         2^-1 A+2^-1 (A+0)=0.100111
    • 第五步:0•A +2^-1 [A+2^-1 (A+0)] =0.100111
    • 第六步:2^-1{0•A+2^-1 [A+2^-1 (A+0)]}=0.0100111
    • 第七步:A+2^-1{0•A+2^-1 [A+2^-1 (A+0)]}=1.0001111
    • 第八步:2^-1 {A+2^-1[0•A+2^-1 (A+2^-1 (A+0))]}=0.10001111

    上述运算过程可归纳为:

    乘法运算可用移位和加法来实现,当两个四位数相乘,总共需做四次加法和四次移位。

    ②由乘数的末位值确定被乘数是否与原部分积相加,然后右移一位,形成新的部分积;同时,乘数也右移一位,由次低位作新的末位,空出最高位放部分积的最低位。

    ③每次做加法时,被乘数仅仅与原部分积的高位相加,其低位被移至乘数所空出的高位位置。

    计算机很容易实现这种运算规则。用一个寄存器存放被乘数,一个寄存器存放乘积的高位,又用一个寄存器存放乘数及乘积的低位,再配上加法器及其他相应电路,就可组成乘法器。又因加法只在部分积的高位进行,故不但节省了器材,而且还缩短了运算时间。

    3、原码一位乘法

    由于原码表示与真值极为相似,只差一个符号,而乘积的符号又可通过两数符号的逻辑异或求得,因此,上述讨论的结果可以直接用于原码一位乘,只需加上符号位处理即可。

    上图是一个32位乘法器的结构框图,其中32位被乘数放在R2中,运算开始时32位乘数放在R1中,运算结束时64位乘积的高位放在R0中,低位放在R1中,R0和R1串联移位。

    完成这个定点原码一位乘法的运算规则可以用如下图所示的逻辑流程图表示。

    在该乘法过程中,每次操作是根据乘数的一位进行操作,对于32位数的乘法,需要循环32次完成一个乘法操作,因此称为一位乘法。

    例:用原码的乘法方法进行2×3的四位乘法。

    解:在乘法开始之前,R0和R1中的初始值为0000和0011,R2中的值为0010。

    在乘法的第一个循环中,判断R1的最低位为1,所以进入步骤1a,将R0的值加上R2的值,结果0010送人R0,然后进入第二步,将R0和R1右移一位,R0、Rl的结果为0001 0001,见下表的循环1,表中黑体字的数据位是乘法过程中判断的R1最低位。

    第二个循环过程中,判断R1的最低位为1,仍进入步骤la,加0010,结果为0011,然后在第二步中将R0和R1右移一位,结果为0001 1000,见下表的循环2。

    第三次循环中,因R1的最低位为0,进入步骤lb,R0不变,第二步移位后结果为00001100,见下表的循环3。

    第四次循环时,仍因R1最低位为0,只作移位,结果为00000110,这就是乘法的结果6,见下表的循环4。

    4、原码两位乘法

    原码两位乘与原码一位乘一样,符号位的运算和数值部分是分开进行的,但原码两位乘是用两位乘数的状态来决定新的部分积如何形成,因此可提高运算速度

    两位乘数共有4种状态,对应这4种状态可得下表。

    表中倍被乘数可通过将被乘数左移一位实现,而3倍被乘数的获得可以分两步来完成,利用3=4-1,第一步先完成减1倍被乘数的操作,第二步完成加4倍被乘数的操作。而加4倍被乘数的操作实际上是由比“11”高的两位乘数代替完成的,可以看作是在高两位乘数上加“1”。这个“1”可暂时存在Cj触发器中。机器完成置“1” Cj即意味着对高两位乘数加1,也即要求高两位乘数代替本两位乘数“11”来完成加4倍被乘数的操作。

    虽然两位乘法可提高乘法速度,但它仍基于重复相加和移位的思想,而且随着乘数位数的增加,重复次数增多,仍然影响乘法速度的进一步提高。采用并行阵列乘法器可大大提高乘法速度。

    原码乘法实现比较容易,但由于机器都采用补码作加减运算,倘若做乘法前再将补码转换成原码,相乘之后又要将负积的原码变为补码形式,这样增添了许多操作步骤,反而使运算复杂。为此,有不少机器直接用补码相乘,机器里配置实现补码乘法的乘法器,避免了码制的转换,提高了机器效率。

    5、补码一位乘法

    一种比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。

    Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作

    判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。

    比如:

    • 第一次判断被乘数0110中的最低位0以及右边的位(辅助位0),得00;所以只进行移位操作;
    • 第二次判断0110中的低两位,得10,所以作减法操作并移位,这个减法操作相当于减去2a的值;
    • 第三次判断被乘数的中间两位,得11,于是只作移位操作;
    • 第四次判断0110中的最高两位,得01,于是作加法操作和移位,这个加法相当于加上8a的值,因为a的值已经左移了三次。

    一般而言,设y=y0,y1y2…yn为被乘数,x为乘数,yi是a中的第i位(当前位)。根据yj与yi+1的值,Booth算法表示如下表所示,其操作流程如下图所示。在Booth算法中,操作的方式取决于表达式(yi+1-yi)的值,这个表达式的值所代表的操作为:

    • 0    无操作
    • +1    加x
    • -1    减x

    Booth算法操作表示

    实现32位Booth乘法算法的流程图

    乘法过程中,被乘数相对于乘积的左移操作可表示为乘以2,每次循环中的运算可表示为对于x(y(i+1)-yi)2^(31-i)项的加法运算(i=31,30,…,1,0)。这样,Booth算法所计算的结果  可表示为:

    例:用Booth算法计算2×(-3)。

    解:[2]补=0010,  [-3]补=1101,在乘法开始之前,R0和R1中的初始值为0000和1101,R2中的值为0010。

    在乘法的第一个循环中,判断R1的最低位和辅助位为10,所以进入步骤1c,将R0的值减去R2的值,结果1110送人R0,然后进人第二步,将R0和Rl右移一位,R0和R1的结果为11110110,辅助位为1。

    在第二个循环中,首先判断Rl的最低位和辅助位为01,所以进入步骤1b,作加法,R0+R2=1111+0010,结果0001送入R0,这时R0R1的内容为0001 0110,在第二步右移后变为0000 1011,辅助位为0。

    在第三次循环中,判断位为10,进入步骤lc,R0减去R2,结果1110送入R0,R1不变;步骤2移位后R0和R1的内容为1111 01011,辅助位为1。

    第四次循环时,因两个判断位为11,所以不作加减运算,向右移位后的结果为1111 1010,这就是运算结果(-6)。

    这个乘法的过程描述如下表所示,表中乘积一栏表示的是R0、R1的内容以及一个辅助位P,黑体字表示对两个判断位的判断。

    用Booth补码一位乘法计算2 ×(-3)的过程

    6、补码两位乘

    补码两位乘运算规则是根据补码一位乘的规则,把比较yiy(i+1)的状态应执行的操作和比较y(i-1)yi 的状态应执行的操作合并成一步,便可得出补码两位乘的运算方法。

    补码两位乘法运算规则如下

    由上表可见,操作中出现加2[x]补和加2[-x]补,故除右移两位的操作外,还有被乘数左移一位的操作;而加2[x]补和加2[-x]补,都可能因溢出而侵占双符号位,故部分积和被乘数采用三位符号位。

    例:[x]补=0.0101,[y]补=1.0101 求: [x• y]补。

    解:求解过程如下表所示。其中乘数取两位符号位即11.0101,[-x]补=1.1011取三符号位为111.1011。

    故[x• y]补=1.11001001

    可见,与补码一位乘相比,补码两位乘的部分积多取一位符号位(共3位),乘数也多取一位符号位(共2位),这是由于乘数每次右移2位,且用3位判断,故采用双符号位更便于硬件实现。可见,当乘数数值位为偶数时,乘数取2位符号位,共需作n/2次移位,最多作n/2+1次加法,最后一步不移位;当n为奇数时,可补0变为偶数位,以简化逻辑操作。也可对乘数取1位符号位,此时共作n/2+1次加法和n/2+1次移位(最后一步移一位)。

    对于整数补码乘法,其过程与小数乘法完全相同。为了区别于小数乘法,在书写上可将符号位和数值位中间的“.”改为“,”即可。

    https://wenku.baidu.com/view/22b2b63231126edb6f1a10bf.html

    二、除法运算

    1.分析笔算除法

    以小数为例,设 x=-0.1011,y=0.1101,求x/y

    笔算除法时,商的符号心算而得:负正得负;其数值部分的运算如下面竖式。

    所以商x/y=0.1101,余数=-0.00000111

    其特点可归纳如下:

    每次上商都是由心算来比较余数(被除数)和除数的大小,确定商为1还是0。

    每做一次减法,总是保持余数不动,低位补0,再减去右移后的除数。

    商符单独处理。如果将上述规则完全照搬到计算机内,实现起来有一定困难,主要问题是:

      a.机器不能“心算”上商,必须通过比较被除数(或余数)和除数绝对值的大小来确定商值,即|x|-|y|,若差为正(够减)上商1,差为负(不够减)上商0。

      b.按照每次减法总是保持余数不动低位补0,再减去右移后的除数这一规则,则要求加法器的位数必须为除数的两倍。仔细分析发现,右移除数可以用左移余数的办法代替,其运算结果是一样的,但对线路结构更有利。不过此刻所得到的余数不是真正的余数,只有将它乘上2^-n才是真正的余数。

      c.笔算求商时是从高位向低位逐位求的,而要求机器把每位商直接写到寄存器的不同位也是不可取的。计算机可将每一位商直接写到寄存器的最低位,并把原来的部分商左移一位。

    综上所述便可得原码除法运算规则。

    2、原码除法

    原码除法和原码乘法一样,符号位是单独处理的。以小数为例:

    式中为x的绝对值,记作x*

    为y的绝对值,记作y*

    即商符由两数符号位“异或”运算求得,商值由两数绝对值相除(x*/y*)求得。

    小数定点除法对被除数和除数有一定的约束,即必须满足下列条件:

       0<|被除数| ≤ |除数|

    实现除法运算时,还应避免除数为0或被除数为0。前者结果为无限大,不能用机器的有限位数表示;后者结果总是0,这个除法操作等于白做,浪费了机器时间。至于商的位数一般与操作数的位数相同。

    原码除法中由于对余数的处理不同,又可分为恢复余数法和不恢复余数法(加减交替法)两种。

    (1)恢复余数法

    恢复余数法的特点是:当余数为负时,需加上除数,将其恢复成原来的余数。

    由上所述,商值的确定是通过比较被除数和除数的绝对值大小,即x*-y*实现的, 而计算机内只设加法器, 故需将x*-y*操作变为[x*]补+[-y*]补的操作。

    例:已知:x=-0.1011,y=-0.1101,求:[x÷y]原

    解:由x*=0.1011,[x]原=1.1011

    y*=0.1101,[-y]补=1.0011,[y]原=1.1101

    商值的求解过程如下:

    故商值为0.1101

    商的符号位为

    由此可见,共上商5次,第一次上的商在商的整数位上,这对小数除法而言,可用它作溢出判断。即当该位为“1”时,表示此除法为溢出,不能进行,应由程序进行处理;当该位为“0”时,说明除法合法,可以进行。

    在恢复余数法中,每当余数为负时,都需恢复余数,这变延长了机器除法的时间,操作也很不规则,对线路结构不利。加减交替法可克服这些缺点。

    (2)加减交替法

    加减交替法又称不恢复余数法,可以认为它是恢复余数法的一种改进算法。

    分析原码恢复余数法得知:

    • 当余数Ri>0时,可上商“1”,再对Ri左移一位后减除数,即2Ri-y*。
    • 当余数Ri>0时,可上商“0”,然后再做Ri+y*,即完成恢复余数的运算,再做2(Ri+y*)-y*,也即2Ri+y*。

    可见,原码恢复余数法可归纳为:

    • 当余数Ri>0时,商上“1”,做2Ri-y*的运算;
    • 当余数Ri<0时,商上“0”,做2Ri+y*的运算。

    这里已看不出余数的恢复问题了,而只是做加y*或减y*,因此,一般把它叫做加减交替法或不恢复余数法。

    例:已知:x=-0.1011,y=-0.1101,求:[x÷ y]原

    解:[x]原=1.1011, x*=0.1011

    [y]原=0.1101,y*=0.1101,[-y*]补=1.0011

    商值的求解过程如下表所示:

    商的符号位为

    所以

    分析此例可见,n位小数的除法共上商n+1次,第一次商用来判断是否溢出。

    倘若比例因子选择恰当,除数结果不溢出,则第一次商肯定是0。如果省去这位商,只需上商n次即可,此时除法运算一开始应将被除数左移一位减去除数,然后再根据余数上商。

    (3)原码加减交替法所需的硬件配置

    下图是实现原码加减交替除法运算的基本硬件配置框图

    图中A、X、Q均为n+1位寄存器,其中A存放被除数的原码,X存放除数的原码。

    移位和加控制逻辑受Q的末位Qn控制。(Qn=1作减法,Qn=0作加法),计数器C用于控制逐位相除的次数n,GD为除法标记,V为溢出标记,S为商符。

    (4)原码加减交替除法控制流程

    下图为原码加减交替除法控制流程图

    除法开始前,Q寄存器被清0,准备接收商,被除数的原码放在A中,除数的原码放在X中,计数器C中存放除数的位数n。

    除法开始后,首先通过异或运算求出商符,并存于S。

    接着将被除数和除数变为绝对值,然后开始用第一次上商判断是否溢出。

    若溢出,则置溢出标记V为1,停止运算,进行中断处理,重新选择比例因子:若无溢出,则先上商,接着A、Q同时左移一位,然后再根据上一次商值的状态,决定是加还是减除数,这样重复n次后,再上最后一次商(共上商n+1次),即得运算结果。

    对于整数除法,要求满足以下条件:

      0 < |除数| ≤ |被除数|

    因为这样才能得到整数商。通常在做整数除法前,先要对这个条件进行判断,若不满足上述条件,机器发出出错信号,程序要重新设定比例因子。

    上述讨论的小数除法完全适用于整数除法,只是整数除法的被除数位数可以是除数的两倍,且要求被除数的高M位要比除数(n位)小,否则即为溢出。

    如果被除数和除数的位数都是单字长,则要在被除数前面加上一个字的0,从而扩展成双倍字长再进行运算。

    3、补码除法

    与补码乘法类似,也可以用补码完成除法操作。补码除法也分恢复余数法和加减交替法,后者用得较多,在此只讨论加减交替法。

    (1)补码加减交替法运算规则

    补码除法其符号位和数值部分是一起参加运算的,因此在算法上不像原码除法那样直观,主要需解决三个问题:

    • 第一,如何确定商值
    • 第二,如何形成商符
    • 第三,如何获得新的余数

    ① 商值的确定

    欲确定商值,必须先比较被除数和除数的大小,然后才能求得商值。

    a. 比较被除数(余数)和除数的大小

    补码除法的操作数均为补码,其符号又是任意的,因此要比较被除数[x]补和除数[y]补的大小就不能简单地用[x]补减去[y]补。实质上比较[x]补和[y]补的大小就是比较它们所对应的绝对值的大小。同样在求商的过程中,比较余数[Ri]补与除数[y]补的大小,也是比较它们所对应的绝对值。这种比较的算法可归纳为以下两点:

    • 第一,当被除数与除数同号时,做减法,若得到的余数与除数同号,表示“够减”,否则表示“不够减”。
    • 第二,当被除数与除数异号时,做加法,若得到的余数与除数异号,表示“够减”,否则表示“不够减”。

    此算法如下表所示

    b.商值的确定

    补码除法的商也是用补码表示的,如果我们约定商的末位用“恒置1”的舍入规则,那么除末位商外,其余各位的商值对正商和负商而言,上商规则是不同的。因为在负商的情况下,除末位商以外,其余任何一位的商与真值都正好相反。因此,上商的算法可归纳为以下两点:

    • 第一,如果[x]补与[y]补同号,商为正,则“够减”时上商“1”。“不够减”时上商“0”(按原码规则上商)。
    • 第二,如果[x]补与[y]补异号,商为负,则“够减”时上商“0”,“不够减”时上商“1”(按反码规则上商)。

    结合比较规则与上商规则,使可得商值的确定办法,如下表所示

    进一步简化,商值可直接由下表确定

    ② 商符的形成

    在补码除法中,商符是在求商的过程中自动形成的。

    在小数定点除法中,被除数的绝对值必须小于除数的绝对值,否则商大于1而溢出。

    因此,当[x]补与[y]补同号时,[x]补-[y]补所得的余数[R0]补与[y]补异号,商上“0”,恰好与商的符号(正)一致;当[x]补与[y]补异号时,[x]补+[y]补所得的余数[R0]补与[y]补同号,商上“1”,这也与商的符号(负)一致。

    可见,商符是在求商值过程中自动形成的。

    此外,商的符号还可用来判断商是否溢出。

    例如,当[x]补与[y]补同号时,若[R0]补与[y]补同号,上商“l”,即溢出。当[x]补与[y]补异号时,若[R0]补与[y]补异号,上商“0”,即溢出。

    当然,对于小数补码运算,商等于“-1”应该是允许的,但这需要特殊处理,为简化问题,这里不予考虑。

    ③ 新余数[R(i+1)]补的获得

    新余数[R(i+1)]补的获得方法与原码加减交替法极相似,其算法规则为:

    • 当[R0]补与[y]补同号时,商上“1”,新余数 [R(i+1)]补 = 2[Ri]补 - [y]补 = 2[Ri]补 + [-y]补
    • 当[R0]补与[y]补异号时,商上“0”,新余数 [R(i+1)]补 = 2[Ri]补 + [y]补

    将此法列于下表:

    如果对商的精度没有特殊要求,一般可采用“末位恒置1”法,这种方法操作简单,易于实现,而且最大误差仅为2^(-n)。

    例:已知:x=-0.1001, y=+0.1101 求: [x÷y]补

    解:[x]补=1.0111,[y]补=0.1101,[-y]补=1.0011

    运算过程如下:

    所以[x÷y]补 = 1.0101

    (2)补码加减交替法所需的硬件配置

    补码加减交替法所需的硬件配置基本上与原码加减交替法所需的硬件配置相似。

    (3)补码加减交替法的控制流程

    除法开始前,Q寄存器被清0,准备接收商,被除数的补码在A中,除数的补码在x中,计数器C中存放除数的位数M。

    除法开始后,首先根据两操作数的符号确定是作加法还是减法,加(或减)操作后,即上第一次商(商符),然后A、Q同时左移一位,再根据商值的状态决定加或减除数,这样重复”次后,再上一次末位商“1”(恒置“1”法),即得运算结果。

    补充说明几点:

    1. 图中未画出补码除法溢出判断的内容;
    2. 按流程图所示,多作一次加(或减)法,其实末位恒置“1”前,只需移位不必作加(或减)法;
    3. 与原码除一样,图中均未指出对0进行检测,实际上在除法运算前,先检测被除数和除数是否为0,若被除数为0,结果即为0;若除数为0,结果为无穷大,这两种情况都无需继续作除法运算;
    4. 为了节省时间,上商和移位操作可以同时进行。
    展开全文
  • (脚注:This is often called "truncation toward zero".) C99 明确规定了商是向0取整,也就意味着余数的符号与被除数相同,前面的转换算法能正常工作。C99 Rationale ...

    (http://synesis.com.au/publications.html搜 conversions)。他的巧妙之处在于,用一个对称的 digits 数组搞定了负数转换的边界条件(二进制补码的正负整数表示范围不对称)。代码大致如下,经过改写:

    const char* convert(char buf[], int value)

    {

    static char digits[19] =

    { '9', '8', '7', '6', '5', '4', '3', '2', '1',

    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

    static const char* zero = digits + 9; // zero 指向 '0'

    // works for -2147483648 .. 2147483647

    int i = value;

    char* p = buf;

    do {

    int lsd = i % 10; // lsd 可能小于 0

    i /= 10; // 是向下取整还是向零取整?

    *p++ = zero[lsd]; // 下标可能为负

    } while (i != 0);

    if (value < 0) {

    *p++ = '-';

    }

    *p = '/0';

    std::reverse(buf, p);

    return p; // p - buf 即为整数长度

    }

    这段简短的代码对 32-bit int 的全部取值都是正确的(从-2147483648到 2147483647)。可以视为 itoa() 的参考实现,面试的标准答案。

    读到这份代码,我心中顿时升起一个疑虑:《C Traps and Pitfalls》第7.7节讲到,C 语言中的整数除法(/)和取模(%)运算在操作数为负的时候,结果是 implementation-defined。(网上能下载到的一份简略版也有相同的内容,http://www.literateprogramming.com/ctraps.pdf第7.5节。)

    也就是说,如果 m、d 都是整数,

    int q = m / d;

    int r = m % d;

    那么C语言只保证 m == q*d + r。如果 m、d 当中有负数,那么 q 和 r 的正负号是由实现决定的。比如 (-13)/4 == (-3)或 (-13)/4 == (-4) 都是合法的。如果采用后一种实现,那么这段转换代码就错了(因为将有 (-1) % 10 == 9)。只有商向 0 取整,代码才能正常工作。

    为了弄清这个问题,我研究了一番。

    语言标准怎么说 C89

    我手头没有 ANSI C89 的文稿,只好求助于 K&R88,此书第 41 页第 2.5 节讲到 The direction of truncation for / and the sign of the result for % are machine-dependent for negative operands, ...。确实是实现相关的。为此,C89 专门提供了 p() 函数,这个函数算出的商是向 0 取整的,便于编写可移植的程序。我得再去查 C++ 标准。

    C++98

    第 5.6.4 节写到 If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined. C++也没有规定余数的正负号(C++03 的叙述一模一样)。

    不过这里有一个注脚,提到 According to work underway toward the revision of ISO C, the preferred algorithm for integer pision follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.即 C 语言的修订标准会采用和 Fortran 一样的取整算法。我又去查了 C99。

    C99

    第 6.5.5.6 节说 When integers are pided, the result of the / operator is the algebraic quotient with any fractional part discarded. (脚注:This is often called "truncation toward zero".) C99 明确规定了商是向0取整,也就意味着余数的符号与被除数相同,前面的转换算法能正常工作。C99 Rationale (http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf) 提到了这个规定的原因,In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. 既然 Fortran 在数值计算领域都做了如此规定,说明开销(如果有的话)是可以接受的。

    C++0x (x已经确定无疑是个十六进制数了)

    最近的 n2800 草案第 5.6.4 节采用了与 C99 类似的表述:For integeral operands the / operator yields the algebraic quotient with any fractional part discarded; (This is often called truncation towards zero.) 可见 C++ 还是尽力保持与 C 的兼容性。

    小结:C89 和 C++98 都留给实现去决定,而 C99 和 C++0x 都规定商向0取整,这算是语言的进步吧。

    C/C++编译器的表现

    我主要关心 G++ 和 VC++ 这两个编译器。需要说明的是,用代码案例来探查编译器的行为是靠不住的,尽管前面的代码在两个编译器下都能正常工作。除非在文档里有明确表述,否则编译器可能会随时更改实现--毕竟我们关心的就是 implementation-defined 行为。

    G++ 4.4

    http://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html

    GCC always follows the C99 requirement that the result of pision is truncated towards zero.

    G++ 一直遵循 C99 规范,商向0取整,算法能正常工作。

    Visual C++ 2008

    http://msdn.microsoft.com/en-us/library/eayc4fzk.aspx

    The sign of the remainder is the same as the sign of the pidend.

    这个说法与商向0取整是等价的,算法也能正常工作。

    其他语言的规定

    既然 C89/C++98/C99/C++0x 已经很有多样性了,索性弄清楚其他语言是怎么定义整数除法的。这里只列出我(陈硕)接触过的几种常用语言。

    Java

    http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.17.2

    Java 语言规范明确说 Integer pision rounds toward 0. 另外对于 int 整数除法溢出,特别规定不抛异常,且 -2147483648 / -1 = -2147483648 (以及相应的long版本)。

    C#

    http://msdn.microsoft.com/en-us/vcsharp/aa336809.aspx

    C# 3.0 语言规定 The pision rounds the result towards zero. 对于溢出的情况,规定在 checked 上下文中抛 ArithmeticException 异常;在 unchecked 上下文里没有明确规定,可抛可不抛。(据了解,C# 1.0/2.0 可能有所不同。)

    Python

    Python 在语言参考手册的显著位置标明,商是向负无穷取整。Plain or long integer pision yields an integer of the same type; the result is that of mathematical pision with the `floor' function applied to the result.

    http://docs.python.org/reference/expressions.html#binary-arithmetic-operations

    Ruby

    Ruby 的语言手册没有明说,不过库的手册说到也是向负无穷取整。The quotient is rounded toward -infinity.

    http://www.ruby-doc.org/docs/ProgrammingRuby/html/ref_c_numeric.html#Numeric.pmod

    Perl

    Perl 语言默认按浮点数来计算除法,所以没有这个问题。Perl 的整数取模运算规则与Python/Ruby一致。

    http://perldoc.perl.org/perlop.html#Multiplicative-Operators

    不过要注意,use integer; 有可能会改变运算结果,例如。

    print -10 % 3; // => 2

    use integers;

    print -10 % 3; // => -1

    Lua

    Lua 缺省没有整数类型,除法一律按浮点数来算,因此不涉及商的取整问题。

    可以看出,在整数除法的取整问题上,语言分为两个阵营,脚本语言彼此是相似的,C99/C++0x/Java/C# 则属于另一个阵营。既然 Python 和 Ruby 都是用 C 实现的,但是运算规则又自成一体,那么必定能从代码中找到证据。

    Python 的代码很好读,我很快就找到了 2.6.4 版实现整数除法和取模运算的函数 i_pmod()

    http://svn.python.org/view/python/tags/r264/Objects/intobject.c?revision=75707&view=markup

    注意到这段代码甚至考虑了 -2147483648 / -1 在32-bit下会溢出这个特殊情况,让我大吃一惊。宏定义UNARY_NEG_WOULD_OVERFLOW 和函数 int_mul() 前面的注释也值得一读。

    Ruby 的代码要混乱一些,花点时间还是能找到,这是 1.8.7-p248 的实现,注意 fixpmod() 函数。

    http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/tags/v1_8_7_248/numeric.c?view=markup

    注意到 Ruby 的 Fixnum 整数的表示范围比机器字长小1bit,直接避免了溢出的可能。

    硬件实现

    既然 C/C++ 以效率著称,那么应该是贴近硬件实现的。我考察了几种熟悉的硬件平台,它们基本都支持 C99/C++0x 的语意,也就是说新规定没有额外开销。列举如下。(其实我们只关系带符号除法,不过为了完整性,这里一并列出 unsigned/signed 整数除法指令。)

    Intel x86/x64

    Intel x86 系列的 DIV/IDIV 指令明确提到是向0取整,与 C99/C++0x/Java/C# 一致。

    MIPS

    很奇怪,我在 MIPS 的参考手册里没有查到 DIV/DIVU 指令的取整方向,不过根据 Patternson&Hennessy 的讲解,似乎向0取整硬件上实现起来比较容易。或许我没找对地方?

    ARM/Cortex-M3

    ARM 没有硬件除法指令,所以不存在这个问题。Cortex-M3 有硬件除法,SDIV/UDIV 指令都是向0取整。Cortex-M3 的除法指令不能同时算出余数,这很特殊。

    MMIX

    MMIX 是 Knuth 设计的 64-bit CPU,替换原来的 MIX 机器。DIV 和 DIVU 都是向负无穷取整(依据 TAOCP 第1.2.4节的定义,在第一卷 40 页头几行),这是我知道的惟一支持 Python/Ruby 语义的"硬件"平台。

    总结:想不到小小的整数除法都有这么大名堂。一段只涉及整数运算的代码,即便能在各种语法相似的语言里运行,结果也可能完全不同。

    展开全文
  • 本文始发于个人公众号:TechFlow,原创不易,求个关注链接难度Medium描述给定两个整数,被除数和除数,要求在不使用除号的情况下计算出两数的商Given two integers dividend and divisor, divide two integers ...

    本文始发于个人公众号:TechFlow,原创不易,求个关注

    链接

    难度

    Medium

    描述

    给定两个整数,被除数和除数,要求在不使用除号的情况下计算出两数的商

    Given two integers dividend and divisor, divide two integers without using

    multiplication, division and mod operator.

    Return the quotient after dividing dividend by divisor.

    The integer division should truncate toward zero.

    样例 1:

    Input: dividend = 10, divisor = 3

    Output: 3

    复制代码

    样例 2:

    Input: dividend = 7, divisor = -3

    Output: -2

    复制代码

    注意:

    除数和被除数都在32位int的范围内

    除数不为0

    对于超界的情况返回

    equation?tex=2%5E%7B31%7D-1

    Both dividend and divisor will be 32-bit signed integers.

    The divisor will never be 0.

    Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−

    equation?tex=2%5E%7B31%7D,

    equation?tex=2%5E%7B31%7D − 1]. For the purpose of this problem, assume that your function returns

    equation?tex=2%5E%7B31%7D − 1 when the division result overflows.

    题解

    老规矩,我们依然从最简单的情况开始入手。我们都知道,在计算机内部,是二进制的,而二进制是只能进行加减的。所以没错,所有的乘法和除法的操作其实最终都会转换为加减法来进行。对于这道题而言也是一样的,既然禁止我们使用除法,那么我们可以用减法来代替。

    暴力

    最简单的策略就是我们可以用一个循环去不停地减,然后用一个累加器计算到底执行了多少次减法,当不够减的时候则停止。整个流程非常简单,但是我们还需要考虑一下正负号的问题,按照排列组合来看,被除数和除数一共有4中正负号的情况。但我们并不需要考虑那么多,这四种情况可以简单地归并成是否同号两种,然后进一步分析又会发现是否同号的计算过程并没有差别,唯一会影响的只有最后结果的正负号。

    还有一点比较令人在意的是提示当中说的可能会超界的情况,我们来分析一下,其实会超界的可能性只有一个。那就是

    equation?tex=-2%5E%7B31%7D除以-1的情况,会得到

    equation?tex=2%5E%7B31%7D,而32位int的正数范围最大是

    equation?tex=2%5E%7B31%7D-1,所以我们需要在意这个问题。不过好在对于Python而言,int是没有范围的,所以可以忽略这个问题,只需要最后特判一下结果,但是对于C++和Java等语言而言,需要特判一下这个case。

    我们来总结一下上面的过程,我们可以先将除数和被除数全部转化为正数,然后用一个标记flag来记录它们是否同号。再计算完结果之后,需要判断一下结果的范围是否越界,如果越界返回

    equation?tex=2%5E%7B31%7D-1

    代码如下:

    class Solution:

    def divide(self, dividend: int, divisor: int) -> int:

    # 判断是否同号

    flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)

    ret = 0

    # 全部赋值为正

    dividend, divisor = abs(dividend), abs(divisor)

    start = 0

    # 模拟除法

    while start + divisor <= dividend:

    start += divisor

    ret += 1

    # 防止越界,注意只有正数才有可能越界

    return min(ret, (1 << 31) - 1) if flag else -ret

    复制代码

    这个代码当然是没有问题的,但是如果你真的这么提交,那么一定会超时。原因也很简单,当除数非常小,比如是1的时候,那么我们的循环次数就是被除数的大小。当我们给定一个很大的被除数的时候,会超时就是显然的了。

    二进制优化

    接下来讲的这个算法很重要,是快速幂等许多算法的基础,由于本题当中不是进行的幂运算,所以不能称作是快速幂算法,一时间也没有什么好的名字,由于本质上是通过二进制的运算来优化,所以就称为二进制优化吧。

    在讲解算法之前,我们先来分析一下bad case出现的原因。之所以会超时,是因为有可能被除数非常小,比如是1,这个时候我们一位一位地减就非常耗时。那么很自然地可以想到,我们可不可以每次不是减去一个1,而是若干个1,最后把这些减去的数量加起来,是不是会比每次减去一个要更快一些呢?但是还有细节我们不清楚,我们怎么来确定这个每次应该减去的数量呢?如果确定了之后发现不够减,又应该怎么办呢?

    要回答上面这个问题,需要对二进制有比较深入的理解。我们先把刚才的问题放一放,来看一看二进制对于除法的解释。举个简单的例子,比如15 / 3 = 5。我们知道15等于5个3相乘,那么我们把它们都写成二进制。15的二进制是1111,3的二进制是0011,5的二进制是0101,我们重点来看这个5的二进制。

    5的二进制写成0101,展开的话会得到是

    equation?tex=2%5E2%20%2B%202%5E0%20%3D%204%20%2B%201,也就是说我们可以把15看成

    equation?tex=(2%5E2%2B2%5E0)*3,这个式子写成是

    equation?tex=(0*2%5E3%2B1*2%5E2%2B0*2%5E1%2B1*2%5E0)*3%3D15。也就是说我们可以把被除数看成是若干个2的幂乘上除数的和,这就把一个除法问题转化成了加法问题。同样我们把求解商转化成了求解商的二进制表达,二进制表达有了,最后的商无非是再进行一个求和累加即可。

    最后,我们来分析一下,为什么能够优化。因为题目当中已经限定了,除数和被除数都在32位的int范围。也就是说最多只有32个二进制位,那么我们的循环次数最多也就是32次。通过二进制优化,我们把原本一个

    equation?tex=O(n)的问题,降级成了

    equation?tex=O(%5Clog%20n),这两者之间差了不止一个数量级,当然要快得多。

    我们把上面这个思路写成代码,就可以得到答案:

    class Solution:

    def divide(self, dividend: int, divisor: int) -> int:

    # 前面处理和之前一样

    flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)

    ret = 0

    dividend, divisor = abs(dividend), abs(divisor)

    # 预处理二进制数组

    binary = [0 for _ in range(33)]

    # 第0位即2的零次方乘上除数,所以就是除数本身

    binary[0] = divisor

    for i in range(1, 33):

    # 后面每一位是前面一位的两倍,因为二进制

    # << 是位运算左移操作,等价于*2,但是速度更快

    binary[i] = binary[i-1] << 1

    for i in range(32, -1, -1):

    if binary[i] <= dividend:

    dividend -= binary[i]

    # 答案加上2^i

    ret += (1 << i)

    return min(ret, (1 << 31) - 1) if flag else -ret

    复制代码

    这段代码不长,也没有用到什么特别牛哄哄的算法,无非是对二进制的一些运用。但是对于对二进制不够熟悉的初学者而言,想完全搞明白可能有些费劲,这也是很正常的。希望大家能够沉下心来好好理解,如果实在看不懂也没关系,在以后快速幂等算法当中,还会和它见面的。

    今天的文章就是这些,如果觉得有所收获,请顺手扫码点个关注吧,你们的举手之劳对我来说很重要。

    展开全文
  • 用VF做在同一循环结构中计算100以内的奇数和 和一百以内的偶数和store0tosume,sumofori=1to100...奇数累加endifnext"1~100偶数累加和=",sume编程计算100以内能3整除的自然数之和.#includemain(){intsum,i;for(i=...
  • 大数法 C语言

    2021-05-23 12:01:09
    看大数除法有点苦逼,找了好几篇博客,都感觉难以理解,今天终于弄懂了大数除法的核心:把除法运算转化减法运算,根据除法运算的特点,不停的用除数位首(从除数第一位开始与被除数位数相等的那几位)减去被除数,...
  • 最近由于项目的需求,需要频繁地拉取不同数据库中的数据,拉取...总结一下这期间遇到的部分问题:1、Mysql中前边有0的数据,0会舍去的问题如一条数据0371xxx,存入数据库后数据变为371xxx(1)如果字段类型必须in...
  • 等实习定下来后,一定补上~~~(1)1与0的特性:1是任何整数的约数,即对于任何整数a,总有1|a.0是任何非零整数的倍数,a≠0,a整数,则a|0.(2)若一个整数的末位是0、2、4、6或8,则这个2整除。(3)若一个整数...
  • list-style:list-style-image || list-style-position || list-style-type当 list-style-image 和 list-style-type ...除非 list-style-image 设置 none 或指定 url 地址的图片不能显示。对应的脚本特性 list-...
  • 匹配0个或1个由前面的正则表达式定义的片段,非贪婪方式 \w 匹配数字字母下划线 \W 匹配非数字字母下划线 所以,[\W_]+代表着匹配一个或多个非数字字母, 如果,我们将[\W_]+变成[\w_]+,那么就代表着匹配一个或多...
  • C语言将字符串转数字

    2021-05-18 09:16:48
    C字符函数列表:atof(将字符串转换成浮点型)atoi(将字符串转换成整型)atol(将字符串转换成长整数)strtod(将字符串转换成浮点数)strtol(将字符串转换成长整型)strtoul(将字符串转换成无符号长整型)toascii...
  • 链接难度Medium描述给定两个整数,被除数和除数,要求在不使用除号的情况下计算出两数的商Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator...
  • SQL语句 不足位数补0

    千次阅读 2020-12-24 05:45:38
    这样就可以了 [注意] 1.'AAA'待补字符:5表示补齐后的总字符长度:0表示不足时补什么字符 2.rpad是右侧补0,左侧补0可用lpad… 1.SQL找不同位数 select length(aae135),count(1) from ac01 group by length(aae135)...
  • 引言在数字计算中,加、减、乘、除运算经常使用。在FPGA中,有加、减、乘、除的算法指令...因此,作者根据二进制乘法的原理,采用被除数与除数的倒数相乘的方法来实现二进制的除法。1 十六位二进制乘法二进制乘法是...
  • java法及java法运算的基础知识

    千次阅读 2020-12-22 18:21:33
    法运算看起来很简单,一般人都会吧,如果不是...不好找的原因主要是问题的偶然性太强,如果你知道可能发生什么问题,你的代码就可以写得更安全。数学法规定,0不能做除数,因为会得到一个无穷大数据。下面看看J...
  • 尝试这个:new BigDecimal("12345678901234567890123456789012345678901234567890").toString(2);编辑:原则上,不同数量系统之间的转换是重复的“法,...取余模3 – 将这个数字加到结果前面.>除以3.>如果...
  • 法啰嗦的,不仅是python。整数除以整数看官请在启动idle之后,练习下面的运算:>>> 2/50>>> 2.0/50.4>>> 2/5.00.4>>> 2.0/5.00.4看到没有?麻烦出来了,如果从小学数学知识...
  • 1. /是精确法,//是向下取整法,%是求模2. %求模是基于向下取整法规则的3. 四舍五入取整round, 向零取整int, 向下和向上取整函数math.floor, math.ceil4. //和math.floor在CPython中的不同5. /在python 2 中是...
  • 1、数字逻辑实验报告(2)数字逻辑实验2一、无符号的乘法器设计50%二、无符号法器设计50%总成绩评语:(包含:预习报告内容、实验过程、实验结果及分析)教师签名姓 名: 学 号: 班 级: 指 导 教 师: 计算机...
  • 分数法的计算方法

    2021-07-02 00:09:36
    课 时 授 课 计 划章节题目二、分数法(1~1)教学目的1理解分数法的意义,掌握分数法的计算方法。2进一步培养学生抽象概括的能力和计算能力。3进一步渗透转化的数学思想。教学重点理解分数法的意义,掌握分数...
  • 分数法怎么算

    2021-06-26 07:16:15
    使学生掌握法估算的方法,会进行两位法估算.2.培养学生估算的意识,归纳概括、迁移类推的能力,以及应用所学知识灵活解决实际问题的能力.3.培养学生学习数学的兴趣,自主探索、勇于尝试的勇气,感受数学...
  • 计算机中的存储

    2021-07-25 00:56:20
    计算机中的存储1、计算机的存储单元计算机内有很多存储单元,计算机用这些存储单元存储数据,一个存储单元可以存储一个八位的二进制,一个存储单元又称作一个字节,记作1B。计算机的处理器一次可以处理的字节...
  • 在进行数字信号处理的时候,计算是必不可少的,通常情况下,能够不用乘法器和法器就不用乘除法器,可以采用移位和加减法的方式来完成计算。但在一些特殊情况下,希望采用乘法,这时候在FPGA当中就需要专用的IP了...
  • 编译器会对除数已知的法进行优化,使用倒数相乘和移位的方法,用消耗时钟周期少的imul和mul指令代替div和idiv指令。
  • 1、数字逻辑实验报告(2)数字逻辑实验2一、无符号的乘法器设计50%二、无符号法器设计50%总成绩评语:(包含:预习报告内容、实验过程、实验结果及分析)教师签名姓 名: 学 号: 班 级: 指 导 教 师: 计算机....
  • 对计算机来说,法与求模是整数算术运算中最复杂的运算。相对其他运算(如加法与...在非嵌入式领域,因为 CPU 运算速度快、存储器容量大,所以执行法运算和求模运算消耗的这些资源对计算机来说不算什么。但是在嵌...
  • 【 前言】有余数的法是位于三下第二章《除数是一位法》中较后面的部分,是对法竖式运算理解模式的一个完型,这堂课整体是建立在师生对话的基础上的,以学生中心,老师引导者和主持者。【课前准备】何...
  • matlab中乘法“*”和点乘“.*”;法“/”和点“./”的联系和区别...2,在处理矩阵乘矩阵时,*表示普通的矩阵乘法,要求前面矩阵的列等于后面矩阵的行数;.*表示两个矩阵对应元素相乘,要求两个矩阵行数列都...
  • 在大数运算中,比较难实现的应该是高精度/高精度的法器。 一、原理 1.大数存储 先说说大数在C语言程序中是怎么存储的。我们使用长度N的int数组来存储无符号超长整数,其中数组每个元素存储的值上限M。如下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 392,306
精华内容 156,922
关键字:

为什么前面的叫被除数