Комбинированная операция умножения на 64-разрядное целое число без знака переполнения

Question

Мне нужно рассчитать

result = (dividend * factor) / divisor

где

dividend: full range of int64_t values
factor: either a full range of uint32_t values or as a special case 2^32
divisor: positive values of int64_t
result: is guaranteed to fit in a int32_t

Мне нужно сделать это простым C/C++ без каких-либо библиотек на микроконтроллере. Компилятор поддерживает типы int64_t и uint64_t; скорее всего, нет аппаратной реализации для умножения или деления. В настоящее время у меня есть обходной путь для фактора uint32_t, но мне нужно решение для фактора 2^32.

Answer 1

ОП: "В настоящее время у меня есть обходной путь для фактора uint32_t"

factor == 2^32 это угловой случай, и это все, что необходимо решить здесь, так как "обходной путь" ОП может обрабатывать факторы [0 ... 2^32-1],

Если dividend может быть удвоено без переполнения, простое использование factor == 2^31 с двойным dividend,

Если divisor это даже, использовать factor == 2^31 с половиной divisor, @Флюгер

Остальное dividend большой. Напомним, что частное находится в [-2^31 ... 2^31-1] спектр. В общем, произведение большого dividend а также factor == 2^32 дивиденд по divisor будет из int32_t диапазон, так что эти комбинации вне диапазона не имеют значения как "результат: гарантированно вписывается в int32_t".

Приемлемые граничные условия возникают с конечным частным около края int32_t спектр.

 pow(2,63) == 9223372036854775808
 pow(2,62) == 4611686018427387904
 pow(2,32) == 4294967296
 pow(2,31) == 2147483648

 Smallest Dividends   Factor      Largest Divisors       Smallest Quotients 
-4611686018427387905  4294967296  -9223372036854775807   2147483648.00+
-4611686018427387905  4294967296   9223372036854775807  -2147483648.00+  OK
 4611686018427387904  4294967296  -9223372036854775807  -2147483648.00+  OK
 4611686018427387904  4294967296   9223372036854775807   2147483648.00+

После тестирования dividend а также divisorединственный представимый ответ в INT32_MIN,

---

Образец кода:

int32_t muldiv64(int64_t dividend, uint64_t factor, int64_t divisor) {
  if (factor >= 0x100000000) {
    assert(factor == 0x100000000);
    factor /= 2;
    if (dividend >= INT64_MIN/2 && dividend <= INT64_MAX/2) {
      dividend *= 2;
    } else if (divisor %2 == 0) {
      divisor /= 2;
    } else {
      return INT32_MIN;
    }
  }
  return  workaround_for_the_uint32_t_factor(dividend, factor, divisor);
}

Первоначальная проблема состоит в том, чтобы обнаружить это краевое состояние и как с ним справиться. workaround_for_the_uint32_t_factor() возможно, еще не был закодирован, поэтому он не был опубликован.