leecode 解题总结：29 Divide Two Integers

#include <iostream>#include <stdio.h>using namespace std;/*问题:Divide two integers without using multiplication, division and mod Operator.If it is overflow, return MAX_INT.分析：除以两个整数不能使用乘法，除法，模运算。溢出需要返回MAX_INT。显然，应该使用位操作了。除法的位操作，例如: 8/2=4, 9/2=4分析: a + b 如果不用除法，需要使用-关键：实际上可以将除法转化为减法，比如9-2=7,7-2=5,5-2=3，3-2=1，1<2，则最后的那一次不算因此总共a / b的结果等于  a-b > b的次数需要先提取出符号，,-9/2=-4那么之所以会溢出：就应该是：减法造成的溢出，而且是两个不同的数相减，提取出符号，让同号数相减就不会溢出输入:8 29 2-9 20 22 0输出:44-40极大值关键：1 除法的溢出问题： -2147483648 / (-1) = 2147483648		if(INT_MIN == dividend && -1 == divisor)		{			return INT_MAX;		}2实际上可以将除法转化为减法，比如9-2=7,7-2=5,5-2=3，3-2=1，1<2，则最后的那一次不算3 long long dvd = labs(dividend);//如果是 -2147483648,会溢出，所以必须用long long，还必须用labs4 可以尝试移动左移除数，使得除数放大，很快到达是否比被除数大的条件，因此，注意每左移一次，放大两倍  减去最大的不超过被除数的左移后的除数后，仍然需要对剩余被除数重复上述操作		long long dvd = labs(dividend);//如果是 -2147483648,会溢出，所以必须用long long，还必须用labs		long long dvs = labs(divisor);		int result = 0;		while( dvd >= dvs )		{			long long temp = dvs;			long long multiple = 1;			while(dvd >= (temp << 1))			{				temp <<= 1;//左移				multiple <<= 1;//结果次数左移			}			dvd -= temp;//被除数减去除数倍数最大值			result += multiple;		}*/class Solution {public:	//dividend:被除数，divisor:除数。24/8=3中，其中24是被除数    int divide(int dividend, int divisor) {		if(0 == divisor)		{			return INT_MAX;		}		if(0 == dividend)		{			0;		}		//除法的溢出问题： -2147483648 / (-1) = 2147483648		if(INT_MIN == dividend && -1 == divisor)		{			return INT_MAX;		}		int symbol;		if( ( dividend >= 0 && divisor >= 0 ) || ( dividend < 0 && divisor < 0 ) )		{			symbol = 1;		}		else		{			symbol = -1;		}		long long dvd = labs(dividend);//如果是 -2147483648,会溢出，所以必须用long long，还必须用labs		long long dvs = labs(divisor);		int result = 0;		while( dvd >= dvs )		{			long long temp = dvs;			long long multiple = 1;			while(dvd >= (temp << 1))			{				temp <<= 1;//左移				multiple <<= 1;//结果次数左移			}			dvd -= temp;//被除数减去除数倍数最大值			result += multiple;		}		result *= symbol;		return result;    }};void PRocess(){	int dividend;	int divisor;	Solution solution;	while(cin >> dividend >> divisor)	{		int result = solution.divide(dividend , divisor);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}