1.题目描述

Divide two integers without using multiplication, division and mod operator.

2.解法分析

不用乘除求模运算，一个很容易让人想到的就是用减法，自然这种算法很费时间，实际上写出一个这样的算法试了一下，TLE。于是剩下的很容易被想到的就是位运算了，这个是基于这样一个观察：

假设除数为B,被除数为A,则有 A = 2^k*B+2^l*B…(其中k>l 且 2^k*B<=A <2^k+1*B)

class Solution {

public:

int divide(int dividend, int divisor) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(divisor==0)return INT_MAX;

long long absDividend=abs((double)dividend);

long long  absDivisor=abs((double)divisor);

long long result=0;

long long maxExpOf2=absDivisor;

long long curResult=1;

while(absDividend>=absDivisor)

{

while(absDividend>=(maxExpOf2<<1))

{

maxExpOf2=maxExpOf2<<1;

curResult=curResult<<1;

}

absDividend-=maxExpOf2;

result+=curResult;

maxExpOf2=absDivisor;

curResult=1;

}

if((dividend>0&&divisor>0)||(dividend<0&&divisor<0))return result;

else return -result;

}

};

 

有了这个思路之后实现起来代码很容易，但是有几个问题需要注意：

• abs函数里面一定要先对里面待转换的参数显式转换一下，否则当参数的二进制表达最高位为1时转换无用
• 为防止溢出，要将类型提升到long long ，如果为了节省空间，可以将类型改为unsigned