Как я обнаруживаю переполнение при умножении два 2's дополнительные целые числа?

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

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

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

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

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

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

РЕДАКТИРОВАТЬ

Да, умножение двух 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 a в третьем столбце, скопируйте и добавьте два нуля = 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 битов для безопасного хранения ответа.Таким образом, это правило служит ответом на вопрос по математике с дополнением до 2-х.

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

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

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

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

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

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

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

Если тип уже является наибольшим, то проверьте, не меньше ли одно из них максимального значения, деленного на другое. Но не берите абсолютное значение! Вместо этого нужна отдельная логика сравнения для каждой из комбинаций знаков negneg, pospos и posneg (negpos, очевидно, может быть сведено к posneg, а pospos может быть сведено к 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);
}