# LeetCode 29 Divide Two Integers（两个整数相除）（*）

## 翻译

不用乘法、除法、取余操作，将两个数相除。

## 原文

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

If it is overflow, return MAX_INT.

## 代码

class Solution {
public:
int divide(int dividend, int divisor) {
if(!divisor) return INT_MAX;
if(divisor == 1) return dividend;
if(divisor == -1) {
if(dividend == INT_MIN) return INT_MAX;
else return -dividend;
}

bool s1 = dividend < 0;
bool s2 = divisor < 0;

unsigned int nom = s1 ? -dividend : dividend;
unsigned int den = s2 ? -divisor : divisor;

unsigned int rem = 0;
unsigned int quot = 0;

for(int i = 31; i >= 0; --i) {
rem <<= 1;
rem |= (nom >> i) & 1;
if(rem >= den) {
rem -= den;
quot |= (1 << i);
}
}

return s1^s2? -quot : quot;
}
};

public class Solution
{
public int Divide(int dividend, int divisor)
{
//1. check overflow: 2 ways of over flow 1) 0 divisor; 2) int.Minvalue/(-1)
if (divisor == 0 || dividend == int.MinValue && divisor == -1) return int.MaxValue;
//2. calculate sign
int sign = dividend > 0 ^ divisor > 0 ? -1 : 1, result = 0;
long m = Math.Abs((long)dividend), n = Math.Abs((long)divisor);
//3. looping from 1 to possible maximum pow(2, x) to add into result
while (m >= n)
{
long subN = n;
for (int subCount = 1; m >= subN; subCount <<= 1, subN <<= 1)
{
m -= subN;
result += subCount;
}
}
return result * sign;
}
}
public class Solution
{
public int Divide(int dividend, int divisor)
{
if (divisor == 1) return dividend;
if (dividend == int.MinValue && divisor == -1 || divisor == 0) return int.MaxValue;
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1, result = 0;
long dvd = Math.Abs((long)dividend), dvs = Math.Abs((long)divisor);
while (dvd >= dvs)
{
long sub = dvs;
int subR = 1;
while (dvd >= (sub << 1))
{ sub <<= 1; subR <<= 1; }
dvd -= sub;
result += subR;
}
return sign * result;
}
}

|
3月前
|

[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
41 0
|
3月前
【Leetcode】两数之和，给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
【Leetcode】两数之和，给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
52 0
|
7天前
|

【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

21 2
|
7天前
|
Python
【Leetcode刷题Python】343. 整数拆分
LeetCode 343题 "整数拆分" 的Python解决方案，使用动态规划算法来最大化正整数拆分为多个正整数之和的乘积。
8 0
|
2月前
|

11 0
|
2月前
|

17 0
|
2月前
|
SQL 算法 数据挖掘

24 0
|
2月前
|
SQL 算法 数据可视化
LeetCode第八题：字符串转换整数 (atoi)【8/1000 python】
LeetCode第八题：字符串转换整数 (atoi)【8/1000 python】
17 0
|
3月前
[leetcode～数位动态规划] 2719. 统计整数数目 hard
[leetcode～数位动态规划] 2719. 统计整数数目 hard
37 6
|
3月前
|

【力扣】7. 整数反转
【力扣】7. 整数反转
26 1