leetcode29两数相除（两数相除什么意思）

给定两个整数，被除数 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 位有符号整数，其数值范围是 [?2^31, 2^31 ? 1]。本题中，如果除法结果溢出，则返回 2^31 ? 1。

package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Divide_29 {
    public int divide(int dividend, int divisor) {
        int res = 0;
        if (dividend == 0) {
            return 0;
        }
        boolean isPositive = false;
        if (dividend > 0) {
            isPositive = true;
        }
        boolean isSame = false;
        if (dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0) {
            isSame = true;
        }

        int now = 0;
        if (isSame) {
            now += divisor;
        } else {
            now -= divisor;
        }
        List<Integer> doubles = new ArrayList<>();
        doubles.add(now);
        while (isPositive && dividend >= now ||
                !isPositive && dividend <= now) {
            if (now > 0 && now > Integer.MAX_VALUE - now ||
                    now < 0 && now < Integer.MIN_VALUE - now) {
                break;
            }
            now += now;
            doubles.add(now);
        }

        int value = 0;
        for (int i = doubles.size() - 1; i >= 0; i--) {
            if (isPositive && value <= dividend - doubles.get(i)
                    || !isPositive && value >= dividend - doubles.get(i)) {
                value = value + doubles.get(i);
                if (isSame) {
                    if (i == 31) {
                        res = Integer.MAX_VALUE;
                    } else {
                        res += 1 << i;
                    }
                } else {
                    res += -1 << i;
                }
                if (value == dividend) {
                    return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Divide_29 divide_29 = new Divide_29();
        int divide = divide_29.divide(2147483647, 3);
        System.out.println(divide);
    }
}