Как вы обнаруживаете переполнение умножения комплемента 2?

Question

В одной из книг, которые я читаю, следующая функция используется для определения переполнения целочисленного умножения дополнения 2.

int tmult_ok(int x, int y) {
int p = x*y;
return !x || p/x == y;
}

Пока это работает, как мне доказать его правильность во всех случаях?Как мне убедиться, что p! = X * y при переполнении?

Вот что я понимаю:

1. Когда вы умножаете 2 целых числаразмер "w-биты", результат может быть 2w бит.
2. Вычисление усекает w биты более высокого порядка.Таким образом, мы остались с битами младшего разряда.3. Позвольте нам сказать, что P = младшие w-биты
3. Затем нам нужно доказать, что (P / x! = Y) и (P / y! = X) при переполнении.
4. Мое замешательство лежит здесь.Как вы можете сказать это (P / x! = Y), когда нет переполнения?Разве не возможно, что битовая комбинация P при делении на x может дать y, даже если есть переполнение?

Answer 1

tmult_ok(x, y) терпит неудачу в любое время x*y в int p = x*y; переполняется, поскольку это неопределенное поведение (UB).
Он также терпит неудачу в угловом регистре, как tmult_ok(INT_MIN, -1) по той же причине.
Это не переносимо "работает".

Альтернатива (и другие для /, -, + ), которая не зависит от дополнения 2.Обратите внимание, что это возвращает противоположность tmult_ok().

int is_undefined_mult1(int a, int b) {
  if (a > 0) {
    if (b > 0) {
      return a > INT_MAX / b;       // a positive, b positive
    }
    return b < INT_MIN / a;         // a positive, b not positive
  }
  if (b > 0) {
    return a < INT_MIN / b;         // a not positive, b positive
  }
  return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}

---

Как я могу гарантировать, что p! = X * y при переполнении?

Переносимый код не может.С целочисленной математикой со знаком в C, переполнение UB.Код должен обнаружить потенциальное переполнение без предварительного умножения. @ Квентин @ Евгений Ш.

---

как мне доказать его правильность во всех случаях?

Сформируйте контрольный тест с использованием математики 2x.Если int является 32-битным, сравните tmult_ok() с умножением с использованием 64-битной математики и посмотрите, находится ли продукт в диапазоне. @ rici

int tmult_ok_ll(int x, int y) {
  long long prod = x;
  prod *= y;
  return (prod >= INT_MIN && prod <= INT_MAX);
}

Попытка всех комбинаций - это грубый метод - вероятно, слишком долго для 32-битного int.

Попробуйте подмножество всех комбинаций,для каждого x,y попробуйте INT_MIN, INT_MIN-1, INT_MIN-2, -2,-1, 0, 1, 2, , INT_MAX-1, INT_MAX.(10 * 10 тестов)

Также подмножество всех комбинаций, для каждого значения +/- в пределах 2 от sqrt(INT_MAX).(10 * 10 тестов)

Также было бы разумно несколько миллионов случайных значений в диапазоне int.

Этого может быть недостаточно, однако, если код проходит это, очень малооставлены угловые случаи - которые очень зависят от вашего исходного кода.

См. также @ Eric Postpischil

Answer 2

Вы можете проверить флаг переполнения (https://en.wikipedia.org/wiki/Overflow_flag)

). В процессорах компьютеров флаг переполнения (иногда называемый флагом V) обычно представляет собой один бит в регистре состояния системы, используемый для указания, когдав операции произошло арифметическое переполнение, указывающее, что результат со знаком дополнения до двух не будет соответствовать количеству битов, используемых для операции (ширина ALU).

Пример доступа к нему:https://www.linuxquestions.org/questions/programming-9/c-how-to-check-the-overflow-flag-930420/#post4612830

Answer 3

* Переполнение

как переполнение - неопределенное поведение, означающее, что компилятор может учитывать, что они никогда не происходят, и упрощать код, который зависит от него. Поэтому вы не можете определить, произошло ли переполнение

, вместо этого следует проверить, выполняет ли операцияпереполнение может переполниться

int tmult_ok(int x, int y) {
  if (MAX_INT / y >= x)
    //throw somthing
  return x*y;
}