本文共 2013 字,大约阅读时间需要 6 分钟。
题目描述
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3 解释: 10/3 = truncate(3.33333…) = truncate(3) = 3 示例 2:输入: dividend = 7, divisor = -3
输出: -2 解释: 7/-3 = truncate(-2.33333…) = -2提示:
被除数和除数均为 32 位有符号整数。
除数不为 0。 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/divide-two-integers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。C++
用减法会超时哦class Solution { public://用减法 int divide(int dividend, int divisor) { if(dividend==0) return 0; if(divisor==1) return dividend; if(dividend==INT_MIN && divisor==-1) return INT_MAX; long res=0; long thisdividend=fabs(dividend); long thisdivisor=fabs(divisor); while(thisdividend>=thisdivisor){ thisdividend-=thisdivisor; res++; } if(dividend<0 && divisor<0 || dividend>0 && divisor>0) return res; return (-1)*res; }};
大佬方法,位运算,不超时
因为计算机在做位移时效率特别高,向左移1相当于乘以2,向右位移1相当于除以2。我们可以把一个dividend(被除数)先除以2n,n最初为31,不断减小n去试探,当某个n满足dividend/2n>=divisor时,表示我们找到了一个足够大的数,这个数*divisor是不大于dividend的,所以我们就可以减去2^n个divisor,以此类推。class Solution { public://用减法 int divide(int dividend, int divisor) { if(dividend==0) return 0; if(divisor==1) return dividend; if(dividend==INT_MIN && divisor==-1) return INT_MAX; bool negative; negative=(dividend^divisor)<0;// 符号相同的时候,negativ为False; long thisdividend=abs((long)dividend); long thisdivisor=abs((long)divisor); int res=0; //找到最大的n使得 divisor*2^n<=dividend for(int i=31;i>=0;i--){ if((thisdividend>>i)>=thisdivisor){ res+=1<
判断异或的结果是否小于0,如果两个整数的符号位相反,那么异或的结果就会让最高位的符号位为1,也就是异或得到的数会小于0,反之大于等于0则表示两个正数符号位相同。