Как определить переполнение при умножении двух целых чисел на 2?

Question

Я хочу умножить два числа и определить, не было ли переполнения. Какой самый простой способ сделать это?

Answer 1

Умножение двух 32-битных чисел дает 64-битный ответ, две 8 дают 16 и т. Д. Двоичное умножение просто сдвигается и складывается. так что если вы указали два 32-битных операнда и бит 17, установленный в операнде A, и любой из битов выше 15 или 16, установленного в операнде b, вы переполните 32-битный результат. бит 17 сдвинут влево 16, бит 33 добавлен к 32.

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

EDIT

Да, умножение двух 3-битных чисел приведет к 5-битному или 6-битному номеру, если в добавлении есть перенос. Аналогично, 2-битный и 5-битный могут привести к 6 или 7 битам и т. Д. Если причина этого вопроса состоит в том, чтобы увидеть, есть ли в вашей переменной результата место для ответа, тогда это решение будет работать и относительно быстро для большинства языки на большинстве процессоров. Это может быть значительно быстрее для одних и значительно медленнее для других. Обычно достаточно быстро (в зависимости от того, как это реализовано) просто посмотреть на количество бит в операндах. Удвоение размера самого большого операнда - безопасная ставка, если вы можете сделать это на своем языке или процессоре. Деления просто дорогие (медленные), и большинство процессоров не имеют один намного меньше при произвольном удвоении размеров операндов. Самым быстрым, конечно, является переход к ассемблеру, который выполняет умножение, и просмотр бита переполнения (или сравнение одного из регистров результата с нулем). Если ваш процессор не может выполнить умножение на оборудовании, он будет медленным независимо от того, что вы делаете. Я предполагаю, что asm не правильный ответ на этот пост, несмотря на то, что он является самым быстрым и имеет самый точный статус переполнения.

двоичное делает умножение тривиальным по сравнению с десятичным, например, взять двоичные числа

0b100 *
0b100 

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

  000 : 0 * 100
 000  : 0 * 100
100   : 1 * 100

Сложите столбцы и получите ответ 0b10000

То же, что и десятичная математика «1 в столбце сотен» означает копирование верхнего числа и добавление двух нулей, оно работает так же и в любой другой базе. Таким образом, 0b100, умноженное на 0b110, равно 0b1000, единица во втором столбце, поэтому скопируйте и добавьте ноль + 0b10000, единицу в третьем столбце, скопируйте и добавьте два нуля = 0b11000.

Это приводит к рассмотрению наиболее значимых битов в обоих числах. 0b1xx * 0b1xx гарантирует, что к ответу добавляется 1xxxx, и это самая большая битовая позиция в добавлении, никакие другие одиночные входы для окончательного добавления не содержат этот столбец или более значимый столбец. Оттуда вам нужно только больше бит на случай, если добавление других битов вызовет перенос.

Что случается с наихудшим случаем, все раз, все, 0b111 * 0b111

 
0b00111 +
0b01110 +
0b11100 

Это вызывает бит переноса в сложении, что приводит к 0b110001. 6 бит 3-битный операнд умноженный на 3-битный операнд 3 + 3 = 6 6-битный наихудший случай.

Таким образом, размер операндов, использующих старший значащий бит (не размер регистров, содержащих значения), определяет требования к памяти в худшем случае.

Ну, это правда, если положительные операнды. Если вы считаете, что некоторые из этих чисел отрицательны, это меняет дело, но не намного.

Минус 4 раза 5, 0b1111 ... 111100 * 0b0000 .... 000101 = -20 или 0b1111..11101100

требуется 4 бита, чтобы представить минус 4, и 4 бита, чтобы представить положительные 5 (не забывайте свой бит знака). Наш результат потребовал 6 бит, если вы удалили все знаковые биты.

Давайте посмотрим на 4-битные угловые корпуса

-8 * 7 = -56
0b1000 * 0b0111 = 0b1001000 
-1 * 7 = -7 = 0b1001
-8 * -8 = 64 = 0b01000000
-1 * -1 = 2 = 0b010
-1 * -8 = 8 = 0b01000
7 * 7 = 49 = 0b0110001

Допустим, мы считаем положительные числа самыми значимыми 1 плюс один, а отрицательными - самые значимые 0 плюс один.

-8 * 7 is 4+4=8 bits   actual 7
-1 * 7 is 1+4=5 bits, actual 4 bits
-8 * -8 is 4+4=8 bits, actual 8 bits
-1 * -1 is 1+1=2 bits, actual 3 bits
-1 * -8 is 1+4=5 bits, actual 5 bits
7 * 7 is 4+4=8 bits, actual 7 bits.

Так что это правило работает, за исключением -1 * -1, вы можете видеть, что я назвал минус один бит, потому что плюс один - найти ноль плюс один. В любом случае, я утверждаю, что если бы это была 4-битная * 4-битная машина, как определено, у вас был бы по крайней мере 4 бита результата, и я интерпретирую вопрос так, как мне может понадобиться более 4 бит для безопасного хранения ответа. Таким образом, это правило служит для ответа на этот вопрос для математики дополнения 2s.

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

На самом деле ваш вопрос не указывает, о каком размере переполнения вы говорите. Старый добрый 8086 16 бит 16 бит дает 32-битный результат (аппаратный), он никогда не может переполниться. Как насчет некоторых ARM, которые имеют 32-битные 32-битные 32-битные результаты, которые легко переполнить. Каков размер ваших операндов для этого вопроса, они одинакового размера или они вдвое больше размера ввода? Готовы ли вы выполнить умножение, которое не может сделать аппаратное обеспечение (без переполнения)? Вы пишете библиотеку компилятора и пытаетесь определить, можете ли вы передавать скоростные операнды на аппаратное обеспечение для скорости или вам нужно выполнять математику без аппаратного умножения. Какую вещь вы получите, если вы приведете операнды, библиотека компилятора попытается откинуть операнды обратно перед умножением, конечно, в зависимости от компилятора и его библиотеки. И он будет использовать счетчик битного трюка, определенный для использования аппаратного или программного умножения.

Моя цель состояла в том, чтобы показать, как двоичное умножение работает в удобоваримой форме, чтобы вы могли увидеть, сколько максимального хранилища вам нужно, найдя местоположение одного бита в каждом операнде. Теперь, как быстро вы можете найти этот бит в каждом операнде, это хитрость. Если вы искали минимальные требования к хранилищу, а не максимальные, то это отдельная история, потому что включает каждый из значащих битов в обоих операндах, а не только один бит на операнд, вы должны выполнить умножение, чтобы определить минимальное хранилище. Если вас не волнует максимальный или минимальный объем памяти, вам нужно просто выполнить умножение и искать ненулевые значения, превышающие установленный вами предел переполнения, или использовать деление, если у вас есть время или оборудование.

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

Answer 2

Проверьте, не превышает ли одно максимальное значение, деленное на другое. (Все значения приняты как абсолютные).

2 дополняемость вряд ли имеет к этому отношение, так как умножение переполняется, если x * (2 ⁿ - x)> 2 ^M , что равно (x * 2) ⁿ - x ² )> 2 ^M или x ² <(x * 2 <sup>n - 2 ^M ), поэтому вам все равно придется сравнивать переполненные числа (x ² может переполниться, а результат - нет).

Answer 3

Если ваш номер не относится к наибольшему целочисленному типу данных, вы можете просто сложить их, умножить и сравнить с максимумом исходного типа числа. Например. в Java, умножая два int, вы можете привести их к long и сравнить результат с Integer.MAX_VALUE или Integer.MIN_VALUE (в зависимости от комбинации знаков) перед приведением результата к int.

Если тип уже является самым большим, проверьте, не превышает ли одно максимальное значение, разделенное на другое. Но не принимайте абсолютное значение! Вместо этого вам нужна отдельная логика сравнения для каждой из комбинаций знаков neg neg, pos pos и pos neg (neg pos, очевидно, можно уменьшить до pos neg и pos pos может быть уменьшен до neg * neg). Сначала проверьте 0 аргументов, чтобы разрешить безопасные деления.

Фактический код см. В исходном коде Java MathUtils класса commons-math 2 или ArithmeticUtils из commons-math 3 . Ищите public static long mulAndCheck(long a, long b). Случай для положительных a и b равен

// check for positive overflow with positive a, positive b
if (a <= Long.MAX_VALUE / b) {
    ret = a * b;
} else {
    throw new ArithmeticException(msg);
}

Answer 4

Я хочу умножить два (два дополнительных) числа и определить, не было ли переполнения. Какой самый простой способ сделать это?

На разных языках не указана действительная проверка на переполнение после того, как это произойдет, поэтому требуются предварительные тесты.

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

Ниже ( Ref ) требуется только сравнение и известные пределы целочисленного диапазона. Возвращает 1, если произойдет переполнение продукта, иначе 0.

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
}

---

Это самый простой способ? ИДК, но он завершен и обрабатывает все известные мне случаи.

Answer 5

В C вот несколько тщательно оптимизированных кодов, которые обрабатывают весь диапазон угловых случаев:

int
would_mul_exceed_int(int a, int b) {
  int product_bits;

  if (a == 0 || b == 0 || a == 1 || b == 1) return (0); /* always okay */
  if (a == INT_MIN || b == INT_MIN) return (1); /* always underflow */

  a = ABS(a);
  b = ABS(b);

  product_bits  = significant_bits_uint((unsigned)a);
  product_bits += significant_bits_uint((unsigned)b);

  if (product_bits == BITS(int)) { /* cases where the more expensive test is required */
    return (a > INT_MAX / b); /* remember that IDIV and similar are very slow (dozens - hundreds of cycles) compared to bit shifts, adds */
  }
  return (product_bits > BITS(int));
}

Полный пример с тестовыми примерами здесь

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

Answer 6

Альтернативы решению Павла Шведа ...

Если ваш язык выбора - ассемблер, тогда вы сможете проверить флаг переполнения. Если нет, вы можете написать пользовательскую подпрограмму ассемблера, которая устанавливает переменную, если был установлен флаг переполнения.

Если это неприемлемо, вы можете найти самый значимый бит набора обоих значений (абсолютных значений). Если сумма превышает число битов в целых числах (или без знака), вы получите переполнение, если они умножены вместе.

Надеюсь, это поможет.