29. Разделите два целых числа.

Условие

29. Разделите два целых числа.

Даны два целых числа dividend и divisor. Разделите эти два числа без использования умножения, деления и оператора взятия остатка от деления.

При делении целых чисел дробная часть должна быть усечена до нуля. Например, дробная часть 8.345 будет усечена до 8, а -2.7335 дробная часть — до -2.

Верните частное после деления dividend на divisor.

Примечание: Предположим, что мы имеем дело со средой, которая может хранить только целые числа в диапазоне 32-битных знаковых целых чисел. В этой задаче, если частное строго больше, то вернуть 2^31 - 1, а если частное строго меньше, то вернуть -2^31.

Пример 1: Входные данные: делимое = 10, делитель = 3. Выходные данные: 3. Объяснение: 10/3 = 3,33333, что в усеченном виде дает 3.

Пример 2: Входные данные: делимое = 7, делитель = -3. Выходные данные: -2. Пояснение: 7/-3 = -2,33333, что в усеченном виде дает -2.

Ограничения: -2^31 <= dividend, divisor <= 2^31 - 1 divisor != 0

Ответ

Деление можно выполнить вычитанием удвоенных делителей. Использование отрицательных значений позволяет обработать MinInt32 без выхода за 32-битный диапазон.

Вариант на Go не использует умножение, деление, остаток и расширение до int64:

func divide(dividend, divisor int32) int32 {
    const min int32 = -1 << 31
    const max int32 = 1<<31 - 1
    if divisor == 0 { panic("division by zero") }
    if dividend == min && divisor == -1 { return max }
    negative := (dividend < 0) != (divisor < 0)
    a, b := dividend, divisor
    if a > 0 { a = -a }
    if b > 0 { b = -b }
    var q int32
    for a <= b {
        value, power := b, int32(-1)
        for value >= -(1<<30) && a <= value+value {
            value += value
            power += power
        }
        a -= value
        q += power
    }
    if negative { return q }
    return -q
}

Сумму удваиваем только при безопасном диапазоне. Накопленное частное отрицательное; знак восстанавливается в конце. Единственное положительное переполнение MinInt32 / -1 обработано заранее. Для фиксированных 32 бит циклы ограничены разрядностью; память O(1).