Как найти произведение двоичных чисел

Научитесь: Профессия Python-разработчик
Узнать больше

Для того, чтобы
умножить двоичное число на 2 (десятичная
двойка это 10 в двоичной системе) достаточно
к умножаемому числу справа приписать
один ноль.

Пример 3.3.
Выполнить операцию умножения
10101 * 10 =
101010.

Проверка.

10101 = 1*2⁴
+ 0*2³
+ 1*2² +
0*2¹ +1*2⁰
= 16 + 4 + 1 = 21

101010 =1*2⁵
+ 0*2⁴
+ 1*2³ +
0*2² +1*2¹
+0*2⁰
= 32 + 8 + 2 = 42

21 * 2 = 42.

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

Пример 3.4.
Выполнить
операцию умножения 1011 * 101.

Умножение можно
свести к сумме трёх поразрядных умножений:

1011 * 1 + 1011 * 0 + 1011 *
100 = 1011 +101100 = 110111.

В столбик это же
самое можно записать так:

Проверка:

101 = 5 (десятичное)

1011 = 11 (десятичное)

110111 = 55 (десятичное)

5*11 = 55 верное
равенство

Умножение
двоичных многоразрядных чисел
производится путём образования частичных
произведений и последующего их
суммирования. В соответствии с таблицей
двоичного умножения каждое частичное
произведение равно нулю, если в
соответствующем разряде множителя
стоит 0, или равно множимому, сдвинутому
на соответствующее число разрядов
влево, если в соответствующем разряде
множителя стоит 1. Таким образом, операция
умножения сводится к операциям сдвига
и сложения. Положение точки определяется
так же, как и при умножении десятичных
чисел.

Пример 3.5.
Выполнить операцию умножения 1010.1 на
101.01.

3.4. Деление двоичных чисел

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

Пример 3.6.
Выполнить деление двоичного числа
1010.101 на двоичное число 10.1:

Деление выполняется
по тем же правилам, что и деление в
десятичной системе счисления.

Выше были рассмотрены
три действия и уже понятно, что, в
общем-то, действия над двоичными числами
мало отличаются от действий над
десятичными числами. Разница появляется
только в том, что цифр две, а не десять,
но это только упрощает арифметические
операции. Так же обстоит дело и с делением,
но для лучшего понимания алгоритм
деления разберём более подробно. Пусть
нам необходимо разделить два десятичных
числа, например 234 разделить на 7.

Выделяем справа
(от старшего разряда) такое количество
цифр, чтобы получившееся число было как
можно меньше и в то же время больше
делителя. 2 – меньше делителя, следовательно,
необходимое нам число 23. Затем делим
полученное число на делитель с остатком.
Получаем следующий результат:

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

_{Пример 3.7.
Разделить
10010111(2)
на 101}(2).

Ищем число, от
старшего разряда которое первое было
бы больше чем делитель. Это четырехразрядное
число 1001. Оно выделено жирным шрифтом.
Теперь необходимо подобрать делитель
выделенному числу. И здесь мы опять
выигрываем в сравнении в десятичной
системой. Дело в том, что подбираемый
делитель это обязательно цифра, а цифры
у нас только две. Так как 1001 явно больше
101, то с делителем всё понятно это 1.
Выполним первый
шаг
операции.

Остаток от
выполненной операции 100. Это меньше чем
101, поэтому чтобы выполнить второй
шаг деления,
необходимо добавить к 100 следующую
цифру, это цифра 0. Теперь имеем следующее
число:

1000 больше 101 поэтому
на втором шаге мы опять допишем в частное
цифру 1 и получим следующий результат
(для экономии места сразу опустим
следующую цифру).

Третий шаг.
Полученное число 110 больше 101, поэтому
и на этом шаге мы запишем в частное 1.
Получиться так:

Полученное число
11 меньше 101, поэтому записываем в частное
цифру 0 и опускаем вниз следующую цифру.
Получается так:

Полученное число
больше 101, поэтому в частное записываем
цифру 1 и опять выполняем действия.
Получается такая картина:

Полученный остаток
10 меньше 101, но у нас закончились цифры
в делимом, поэтому 10 это остаток, а 1110
это искомое частное.

Проверим в десятичных
числах

10010011 = 147

101 = 5

10 = 2

11101 = 29

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

From Wikipedia, the free encyclopedia

A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers.

A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve computing the set of partial products, which are then summed together using binary adders. This process is similar to long multiplication, except that it uses a base-2 (binary) numeral system.

History[edit]

Between 1947 and 1949 Arthur Alec Robinson worked for English Electric Ltd, as a student apprentice, and then as a development engineer. Crucially during this period he studied for a PhD degree at the University of Manchester, where he worked on the design of the hardware multiplier for the early Mark 1 computer.
However, until the late 1970s, most minicomputers did not have a multiply instruction, and so programmers used a «multiply routine»^[1][2][3]
which repeatedly shifts and accumulates partial results,
often written using loop unwinding. Mainframe computers had multiply instructions, but they did the same sorts of shifts and adds as a «multiply routine».

Early microprocessors also had no multiply instruction. Though the multiply instruction became common with the 16-bit generation,^[4]
at least two 8-bit processors have a multiply instruction: the Motorola 6809, introduced in 1978,^[5] and Intel MCS-51 family, developed in 1980, and later the modern Atmel AVR 8-bit microprocessors present in the ATMega, ATTiny and ATXMega microcontrollers.

As more transistors per chip became available due to larger-scale integration, it became possible to put enough adders on a single chip to sum all the partial products at once, rather than reuse a single adder to handle each partial product one at a time.

Because some common digital signal processing algorithms spend most of their time multiplying, digital signal processor designers sacrifice considerable chip area in order to make the multiply as fast as possible; a single-cycle multiply–accumulate unit often used up most of the chip area of early DSPs.

Binary long multiplication[edit]

The method taught in school for multiplying decimal numbers is based on calculating partial products, shifting them to the left and then adding them together. The most difficult part is to obtain the partial products, as that involves multiplying a long number by one digit (from 0 to 9):

     123
   x 456
   =====
     738  (this is 123 x 6)
    615   (this is 123 x 5, shifted one position to the left)
 + 492    (this is 123 x 4, shifted two positions to the left)
   =====
   56088

A binary computer does exactly the same multiplication as decimal numbers do, but with binary numbers. In binary encoding each long number is multiplied by one digit (either 0 or 1), and that is much easier than in decimal, as the product by 0 or 1 is just 0 or the same number. Therefore, the multiplication of two binary numbers comes down to calculating partial products (which are 0 or the first number), shifting them left, and then adding them together (a binary addition, of course):

       1011   (this is binary for decimal 11)
     x 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

This is much simpler than in the decimal system, as there is no table of multiplication to remember: just shifts and adds.

This method is mathematically correct and has the advantage that a small CPU may perform the multiplication by using the shift and add features of its arithmetic logic unit rather than a specialized circuit. The method is slow, however, as it involves many intermediate additions. These additions are time-consuming. Faster multipliers may be engineered in order to do fewer additions; a modern processor can multiply two 64-bit numbers with 6 additions (rather than 64), and can do several steps in parallel.^{[citation needed]}

The second problem is that the basic school method handles the sign with a separate rule («+ with + yields +», «+ with − yields −», etc.). Modern computers embed the sign of the number in the number itself, usually in the two’s complement representation. That forces the multiplication process to be adapted to handle two’s complement numbers, and that complicates the process a bit more. Similarly, processors that use ones’ complement, sign-and-magnitude, IEEE-754 or other binary representations require specific adjustments to the multiplication process.

Unsigned integers[edit]

For example, suppose we want to multiply two unsigned eight bit integers together: a[7:0] and b[7:0]. We can produce eight partial products by performing eight one-bit multiplications, one for each bit in multiplicand a:

 p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
 p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0]
 p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0]
 p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0]
 p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0]
 p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0]
 p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0]
 p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]

where {8{a[0]}} means repeating a[0] (the 0th bit of a) 8 times (Verilog notation).

In order to obtain our product, we then need to add up all eight of our partial products, as shown here:

                                                p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
                                        + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
                                  + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0     0
                            + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0     0     0
                      + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0     0     0     0
                + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0     0     0     0     0
          + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0     0     0     0     0     0
    + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0     0     0     0     0     0     0
-------------------------------------------------------------------------------------------
P[15] P[14] P[13] P[12] P[11] P[10]  P[9]  P[8]  P[7]  P[6]  P[5]  P[4]  P[3]  P[2]  P[1]  P[0]

In other words, P[15:0] is produced by summing p0, p1 << 1, p2 << 2, and so forth, to produce our final unsigned 16-bit product.

Signed integers[edit]

If b had been a signed integer instead of an unsigned integer, then the partial products would need to have been sign-extended up to the width of the product before summing. If a had been a signed integer, then partial product p7 would need to be subtracted from the final sum, rather than added to it.

The above array multiplier can be modified to support two’s complement notation signed numbers by inverting several of the product terms and inserting a one to the left of the first partial product term:

                                                    1  ~p0[7]  p0[6]  p0[5]  p0[4]  p0[3]  p0[2]  p0[1]  p0[0]
                                                ~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0]   0
                                         ~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0]   0      0
                                  ~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0]   0      0      0
                           ~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0]   0      0      0      0
                    ~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0]   0      0      0      0      0
             ~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0]   0      0      0      0      0      0
      +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0]   0      0      0      0      0      0      0
 ------------------------------------------------------------------------------------------------------------
P[15]  P[14]  P[13]  P[12]  P[11]  P[10]   P[9]   P[8]   P[7]   P[6]   P[5]   P[4]   P[3]   P[2]   P[1]  P[0]

Where ~p represents the complement (opposite value) of p.

There are many simplifications in the bit array above that are not shown and are not obvious. The sequences of one complemented bit followed by noncomplemented bits are implementing a two’s complement trick to avoid sign extension. The sequence of p7 (noncomplemented bit followed by all complemented bits) is because we’re subtracting this term so they were all negated to start out with (and a 1 was added in the least significant position). For both types of sequences, the last bit is flipped and an implicit -1 should be added directly below the MSB. When the +1 from the two’s complement negation for p7 in bit position 0 (LSB) and all the -1’s in bit columns 7 through 14 (where each of the MSBs are located) are added together, they can be simplified to the single 1 that «magically» is floating out to the left. For an explanation and proof of why flipping the MSB saves us the sign extension, see a computer arithmetic book.^[6]

Floating point numbers[edit]

A binary floating number contains a sign bit, significant bits (known as the significand) and exponent bits (for simplicity, we don’t consider base and combination field). The sign bits of each operand are XOR’d to get the sign of the answer. Then, the two exponents are added to get the exponent of the result. Finally, multiplication of each operand’s significand will return the significand of the result. However, if the result of the binary multiplication is higher than the total number of bits for a specific precision (e.g. 32, 64, 128), rounding is required and the exponent is changed appropriately.

Hardware implementation[edit]

The process of multiplication can be split into 3 steps:^[7][8]

• generating partial product
• reducing partial product
• computing final product

Older multiplier architectures employed a shifter and accumulator to sum each partial product, often one partial product per cycle, trading off speed for die area. Modern multiplier architectures use the (Modified) Baugh–Wooley algorithm,^{[9][10][11][12]} Wallace trees, or Dadda multipliers to add the partial products together in a single cycle. The performance of the Wallace tree implementation is sometimes improved by modified Booth encoding one of the two multiplicands, which reduces the number of partial products that must be summed.

For speed, shift-and-add multipliers require a fast adder (something faster than ripple-carry).^[13]

A «single cycle» multiplier (or «fast multiplier») is pure combinational logic.

In a fast multiplier,
the partial-product reduction process usually contributes the most to the delay, power, and area of the multiplier.^[7]
For speed, the «reduce partial product» stages are typically implemented as a carry-save adder composed of compressors and the «compute final product» step is implemented as a fast adder (something faster than ripple-carry).

Many fast multipliers use full adders as compressors («3:2 compressors») implemented in static CMOS.
To achieve better performance in the same area or the same performance in a smaller area, multiplier designs may use higher order compressors such as 7:3 compressors;^[8][7]
implement the compressors in faster logic (such transmission gate logic, pass transistor logic, domino logic);^[13]
connect the compressors in a different pattern; or some combination.

Example circuits[edit]

See also[edit]

References[edit]

• Hennessy, John L.; Patterson, David A. (1990). «Section A.2, section A.9». Computer Architecture: A quantitative Approach. Morgan Kaufmann. pp. A–3..A–6, A–39..A–49. ISBN 978-0-12383872-8.

External links[edit]

• Multiplier Designs targeted at FPGAs
• Binary Multiplier circuit using Half -Adders and digital gates.

Двоичный калькулятор онлайн

Если вам необходимо произвести математические операции над двоичными числами воспользуйтесь нашим двоичным онлайн калькулятором:

Просто введите целые двоичные числа, выберите операцию и получите результат.

Сложение двоичных чисел

Вычитание двоичных чисел

Умножение двоичных чисел

Деление двоичных чисел

См. также