@Lin--
2018-10-24T15:00:54.000000Z
字数 3084
阅读 334
计算机数学
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.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:Input: dividend = 7, divisor = -3
Output: -2
Note:*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: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
/*
*File:divide.c
*Author:Hongpei lin
*Date:20181024
*Purpose:to solve the problem in Leetcode
*https://leetcode.com/problems/divide-two-integers/description/
*/
#include<stdio.h>
#include<math.h>
#include<limits.h>
/**
* Declaration of functions.
*Input a integer dividend and a integer divisor
*Output a integer that equal dividend/divisor
*Method:this algorithm is divided several circumstances
*0:special circumstances:return special result straight
*1:dividend>0 and divisor>0 return dividend/divisor
*2:dividend>0 and divisor<0
*let divisor=-divisor,so divisor>0,then return dividend/divisor
*3:dividend<0 and divisor>0
*let dividend=-dividend,so dividend>0,then return dividend/divisor
*4:dividend<0 and dividend<0
*let dividend=-dividend,divisor=-divisor
*so dividend>0 and divisor>0
*from circumstance 1rd to circumstance 4th
*include some special circumstances,that return special result
**/
//functions division
//algorithm division by using circular subtraction
int division(int a,int b);
int divide(int dividend,int divisor)
{
//0:
//when dividend=0 or divisor=-2^31 and dividend!=-2^31
//return 0;because no one can divide -2^31 when consider overflow
if(dividend==0||((dividend!=divisor)&&divisor==INT_MIN))return 0;
//if divided=1, result=dividend
if(divisor==1) return dividend;
//if dividend=-2^31 and divisor=-1,result=-dividend=2^31
//but 2^31 is overflow, so result=2^31-1
if(dividend==INT_MIN&&divisor==-1) return 2147483647;
//if divisor=-1, result=-dividend(dividend!=-2^31)
if(divisor==-1)return -dividend;
//if dividend=divisor, result=1
if(dividend==divisor)return 1;
//1:
if(dividend>0&&divisor>0) return division(dividend,divisor);
//2:
else if(dividend>0&&divisor<0)//2
{
divisor=fabs(divisor);
//function "division" just return positive numbers and 0
//but result<0,so let result=-division's result
return -division(dividend,divisor);
}
//3:
else if(dividend<0&&divisor>0)
{
//same process
if(dividend!=INT_MIN)
{
dividend=fabs(dividend);
return -division(dividend,divisor);
}
//if dividend=-2^31
else
{
int result=0;
//let dividend=2^31-1
dividend=INT_MAX;
//compute (2^31-1)/divisor
while(dividend>=divisor)
{
dividend=dividend-divisor;
result++;
}
//rest=|-2^31-(2^31-1)|=1
dividend=dividend+1;
if(dividend==divisor)return -(result+1);
else return -result;
}
}
//4:
//same process
else if(dividend<0&&divisor<0)
{
if(dividend==INT_MIN)
{
dividend=INT_MAX;
divisor=fabs(divisor);
int result=0;
while(dividend>=divisor)
{
dividend=dividend-divisor;
result++;
}
dividend=dividend+1;
if(dividend==divisor)return (result+1);
else return result;
}
else
{
dividend=fabs(dividend);
divisor=fabs(divisor);
return division(dividend,divisor);
}
}
return 0;
}
//function division
int division(int a,int b)
{
int c=0;
while(a>=b)
{
a=a-b;
c++;
}
return c;
}