注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex29 Divide Two Integers  

2015-05-23 22:39:27|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

If it is overflow, return MAX_INT.


这个题和前面一个m->n所有的数字and,有点儿相似,只不过这里要求只能用加法,限制比较多。所以只能一次次加
例如87/4  首先4< 87  4*2 <87   8 *2<87  16 *2<87 一直到  32*2<87但是 64*2>87    总共移动了4位,就是16.还有剩下
87 - 16*4 = 23  接着87替换成23  继续这么做。
具体见代码,类似于二分查找

/*
* 算法的思想是先对dividend去对数,得到N,然后
* dividend -2^n,但是取对数的过程不能用乘法和除法,就只能用加法了
* 每次循环一遍,直到找到被除数可以减掉的最大的一个值,重复计算
*/
class Solution {
public:
int divide1(int dividend, int divisor) {
//上面是某个作者的递归形式,也可以改成非递归形式
//这个题目其实和昨天的那个求m n所有的数字 and的结果很相似
if (dividend == 0 || divisor == 0)
return 0; //处理被除数和除数为0的特殊情况
//处理数字越界的情况

long long int newDividen = dividend;
long long int newDivisor = divisor;
bool flag = false;
if (newDividen*newDivisor < 0)
flag = true;
if (newDividen < 0)
newDividen = 0- newDividen;
if (newDivisor < 0)
newDivisor = 0- newDivisor;

if (newDivisor > newDividen)
return 0;
long long int sum = 0;
int tmp;
long long int count = 1;
long long int last = 0;
while (newDividen >= newDivisor)
{
sum = newDivisor;
count = 1;
while ((sum +sum) <= newDividen)
{
sum = sum +sum;
count = count << 1;
}
newDividen -= sum;
last += count;
}
if (flag)
last = 0 - last;
if (last >= INT_MAX)
return INT_MAX;
return last;
}
};

参考
http://www.cnblogs.com/panda_lin/archive/2013/10/30/divide_two_integers.html
http://www.cnblogs.com/lihaozy/archive/2012/12/30/2840070.html
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017