Ответ 1
Умножение двух 32-битных чисел приводит к 64-битовому ответу, два 8-х дают 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
То же, что и десятичная математика a 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 бит, чтобы безопасно хранить ответ. Таким образом, это правило служит для ответа на этот вопрос для математики дополнения 2s.
Если ваш вопрос состоял в том, чтобы точно определить переполнение, а затем скорость вторична, то для некоторых систем это будет действительно очень медленным, для каждого умножения. Если это вопрос, который вы задаете, чтобы получить некоторую скорость назад, вам нужно настроить его немного лучше для языка и/или процессора. Вы можете удвоить самый большой операнд, если хотите, и проверить ненулевые биты над размером результата или использовать разделить и сравнить. Если вы не можете удвоить размеры операндов, разделите их и сравните. Проверьте нуль перед делением.
На самом деле ваш вопрос не указывает, какой размер переполнения вы говорите. Хороший старый 8086 16 бит раз 16 бит дает 32-битный результат (аппаратное обеспечение), он никогда не может переполняться. Что касается некоторых из ARM, которые имеют 32-разрядный 32-разрядный 32-разрядный 32-разрядный результат, легко переполняется. Каков размер ваших операндов для этого вопроса, они одного размера или они удваивают размер ввода? Готовы ли вы выполнять умножения, которые аппаратное обеспечение не может выполнять (без переполнения)? Вы пишете библиотеку компилятора и пытаетесь определить, можете ли вы поместить операнды на аппаратное обеспечение для скорости или если вам нужно выполнить математику без аппаратного умножения. Что бы вы делали, если вы запустили операнды, библиотека компилятора попытается отбросить операнды назад, прежде чем делать размножение, в зависимости от компилятора и его библиотеки. И он будет использовать счет, который бит трюк определяет для использования аппаратного умножения или программного обеспечения.
Моя цель состояла в том, чтобы показать, как двоичное умножение работает в удобоваримой форме, чтобы вы могли видеть, сколько максимального объема памяти вам нужно, найдя местоположение одного бита в каждом операнде. Теперь, как быстро вы можете найти этот бит в каждом операнде, это трюк. Если вы искали минимальные требования к хранению, а не максимум, это другая история, потому что включает в себя каждый один из значимых битов в обоих операндах, а не один бит на операнд, вам нужно умножить, чтобы определить минимальное хранилище. Если вы не заботитесь о максимальном или минимальном хранении, вам нужно просто умножить и искать ненулевые значения выше определенного предела переполнения или использовать разделитель, если у вас есть время или оборудование.
Ваши тэги подразумевают, что вас не интересует плавающая точка, плавающая точка - совершенно другой зверь, вы не можете применить какое-либо из этих правил с фиксированной точкой к плавающей запятой, они НЕ работают.