Algorithm for multiplication of two binary numbers

Here is a proof by Induction. Let $a=a_1a_2...a_n$ and $b=b_1b_2...b_m$. Observe that $a$ (the same with $b$) can be written as: $a=a_1c_1+a_2c_2+...a_nc_n$ where $c_i$ has 1 in ith position (e.g. $c_4=1000$). Let $ab$ is the result of the product of a and b by grade school algorithm. $ab$ can be written as: $$a_1b_1c_1+a_1b_2c_2+a_1b_3c_3+ .... + a_1b_mc_m + a_2b_1c_2 + a_2b_2c_4 + .... + a_2b_mc_{2m} + ... = \sum_{i=1}^n\sum_{j=1}^ma_ib_jc_{ij}$$Note that $c_{ij}$ has 1 in the (i*j)th position.

Table of Contents Show

Binary Multiplication Rules
How to Multiply Binary Numbers?
Topics Related to Binary Multiplication
Binary Multiplication Examples
FAQs on Binary Multiplication
What are the Rules for Binary Multiplication?
What is the Result of Binary Multiplication of ($111)_{2}$ and ($111)_{2}$?
What are the Steps to do Binary Multiplication?
What is the Product of ($1111)_{2}$ and ($1111)_{2}$ Using Binary Multiplication?
What is Binary Multiplication of Negative Numbers?
What is the Result of Binary Multiplication of the Numbers ($10100)_{2}$ and ($01011)_{2}$?

For basis case: Choose $a=11$ and $b=01$, then $a=a_1(1)+a_2(10)$ and $b = b_1(1)+b_2(10)$. Now, $ab = a_1 b_1(1)+a_1b_2(10)+a_2b_1(10)+a_2b_2(1000)=(1)(1)(1)+(1)(0)(10)+(1)(1)(10)+(1)(0)(1000)=1+10=11$

The induction hypothesis. Suppose that $a$ with $n$ digits and $b$ with $m$ digits gives the product of ab. Now, we want to show that it holds for a with one extra digit and b with one extra digits, i.e. $\bar{a}\bar{b}$ be the new product of a and b with an extra digit in each of them.

Since we defined ab (see above) and the difference between $\bar a$ and $a$ is that $\bar a$ has n+1 digits whereas $a$ has n digits. Thus, $\bar ab= ab + a_{n+1}b_1c_{n+1} + a_{n+1}b_2c_{2(n+1)}+...+ a_{n+1}b_mc_{m(n+1)}$. By multiplication rule, each digit in $a$ must be multiplied by each digit in $b$. Since this is achieved in $\bar ab$ by the grade-school algorithm, then we are done here. Do the same with $\bar{a}\bar{b}$ as following: $\bar{a}\bar{b} =\bar{a}b + b_{m+1}a_1c_{m+1} + b_{m+1}a_2c_{2(m+1)} + ... + b_{m+1}a_{n+1}c_{(n+1)(m+1)}$. It is clear that the multiplication rule holds here, too. Thus, the proof is complete.

Improve Article

Save Article

Like Article

Multiplication of two fixed point binary number in signed magnitude representation is done with process of successive shift and add operation.

In the multiplication process we are considering successive bits of the multiplier, least significant bit first.
If the multiplier bit is 1, the multiplicand is copied down else 0’s are copied down.

The numbers copied down in successive lines are shifted one position to the left from the previous number.
Finally numbers are added and their sum form the product.

The sign of the product is determined from the sign of the multiplicand and multiplier. If they are alike, sign of the product is positive else negative.

Hardware Implementation :
Following components are required for the Hardware Implementation of multiplication algorithm :

Registers:Two Registers B and Q are used to store multiplicand and multiplier respectively.Register A is used to store partial product during multiplication.
Sequence Counter register (SC) is used to store number of bits in the multiplier.
Flip Flop:To store sign bit of registers we require three flip flops (A sign, B sign and Q sign).
Flip flop E is used to store carry bit generated during partial product addition.
Complement and Parallel adder:
This hardware unit is used in calculating partial product i.e, perform addition required.

Flowchart of Multiplication:

Initially multiplicand is stored in B register and multiplier is stored in Q register.
Sign of registers B (Bs) and Q (Qs) are compared using XOR functionality (i.e., if both the signs are alike, output of XOR operation is 0 unless 1) and output stored in As (sign of A register).
Note: Initially 0 is assigned to register A and E flip flop. Sequence counter is initialized with value n, n is the number of bits in the Multiplier.
Now least significant bit of multiplier is checked. If it is 1 add the content of register A with Multiplicand (register B) and result is assigned in A register with carry bit in flip flop E. Content of E A Q is shifted to right by one position, i.e., content of E is shifted to most significant bit (MSB) of A and least significant bit of A is shifted to most significant bit of Q.
If Qn = 0, only shift right operation on content of E A Q is performed in a similar fashion.
Content of Sequence counter is decremented by 1.
Check the content of Sequence counter (SC), if it is 0, end the process and the final product is present in register A and Q, else repeat the process.

Example:

Multiplicand = 10111 Multiplier = 10011

Binary multiplication is the process of multiplying binary numbers. The process of multiplying binary numbers is the same as that of arithmetic multiplication with decimal numbers. The only difference is that binary multiplication involves numbers that are consist of 0s and 1s, whereas, decimal multiplication involves numbers that comprise digits from 0 to 9. Let us learn the process of binary multiplication step by step.

Binary Multiplication Rules

Binary multiplication is similar to the multiplication of decimal numbers. We have a multiplier and a multiplicand. The result of multiplication results in a product. Since only binary digits are involved in binary multiplication, we get to multiply only 0s and 1s. The rules for binary multiplication are as follows.

Multiplicand	Multiplier	Product
0	0	0 × 0 = 0
0	1	0 × 1 = 0
1	0	1 × 0 = 0
1	1	1 × 1 = 1

How to Multiply Binary Numbers?

The process of multiplying binary numbers is similar and easier to do than decimal multiplication as binary numbers consist of only two digits which are 0 and 1. The method of multiplying binary numbers is given below. The same set of rules also apply to binary numbers with a decimal point. Let us take the example of multiplying ($11101)_{2}$ and ($1001)_{2}$. The decimal equivalent of ($11101)_{2}$ is 29 and the decimal equivalent of ($1001)_{2}$ is 9. Now let us multiply these numbers.
Step 1: Write down the multiplicand ($11101)_{2}$ and the multiplier ($1001)_{2}$ one below the other in proper positions.
Step 2: Multiply the rightmost digit or the least significant bit (LSB) of the multiplier (1) with all the digits of the multiplicand ($11101)_{2}$.
Step 3: Add a place holder of '0' or 'X' before multiplying the next higher order digit of the multiplier& with the multiplicand.
Step 4: Repeat the same process for all the next higher-order digits until we reach the most significant bit (MSB) which is the left-most digit of the multiplicand with the multiplier.
Step 5: The product obtained in each row is called the partial product. Finally, add all the partial products. To add all the binary numbers use the rules of binary addition.

(The rules for binary addition are listed as follows: 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 0, with a carryover of 1. So, 1 + 1 = 10 and 1 + 1 + 1 = 11 in the binary number system)

Let us look at the following process of binary multiplication as described above.

Therefore, the product of ($11101)_{2}$ and ($1001)_{2}$ is ($100000101)_{2}$. Let us verify our answer. The decimal equivalent of ($100000101)_{2}$ is 261. To know how to convert a binary number to a decimal number, click here. The decimal equivalent of& ($11101)_{2}$ is 29 and the decimal equivalent of ($1001)_{2}$ is 9. When we multiply 29 and 9 the product is 261. The decimal equivalent of ($100000101)_{2}$ is 261. Hence, the product is correct.

Check out some interesting topics related to binary multiplication.

Binary Multiplication Examples

Example 1: Using the binary multiplication rules, multiply ($110)_{2}$ and ($11)_{2}$.

Solution:

The rules for binary multiplication are: 0 × 0 = 0 0 × 1 = 0 1 × 0 = 0 1 × 1 = 1
Let us use the above rules to multiply the binary numbers.

GIven, multiplicand = $110_{2}$, multiplier = $11_{2}$. We multiply the two numbers as shown below.

Therefore, the product of ($110)_{2}$ and ($11)_{2}$ is ($10010)_{2}$.

Example 2: Using the binary multiplication rules, find the product of ($11011)_{2}$ and ($101)_{2}$.
Solution:

GIven multiplicand = ($11011)_{2}$ and multiplier = ($101)_{2}$
On multiplying we get,

Therefore, the product of ($11011)_{2}$ and ($101)_{2}$ is ($10000111)_{2}$.

Example 3: Using the binary multiplication rules, multiply the binary numbers ($1011.1)_{2}$ and ($10.1)_{2}$.

Solution:

Given multiplicand = ($1011.1)_{2}$ and multiplier = ($10.1)_{2}$.

Therefore, the product of ($1011.1)_{2}$ and ($10.1)_{2}$ is ($11100.11)_{2}$

go to slidego to slidego to slide

Have questions on basic mathematical concepts?

Become a problem-solving champ using logic, not rules. Learn the why behind math with our certified experts

Book a Free Trial Class

FAQs on Binary Multiplication

Binary multiplication is the process of multiplying binary numbers. Binary numbers form the base-2 number system. Data is stored in a computer in the form of 0s and 1s. The process of multiplying binary numbers is the same as that of the arithmetic operation of multiplication which is done on decimal or base-10 numbers. The only difference is that binary numbers consist of 0s and 1s.

What are the Rules for Binary Multiplication?

Binary multiplication is also similar to multiplying base-10 numbers which are (0 to 9). Binary numbers comprise only 0s and 1s. Therefore, we need to know the product when 0 is multiplied with 0 and 1 and 1 is multiplied with 0 and 1. The rules for binary multiplication are as follows.

0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1

What is the Result of Binary Multiplication of ($111)_{2}$ and ($111)_{2}$?

The product of ($111)_{2}$ and ($111)_{2}$ is ($110001)_{2}$.

What are the Steps to do Binary Multiplication?

Binary multiplication of two numbers can be done by following the steps given below.

Step 1: Arrange the multiplier and the multiplicand in proper positions. For example, we may multiply a 3-digit number and a 2- digit number. In this case, the 2-digit number is to be placed correctly below the 3-digit number, like this, 110 × 10 --------

_____

Step 2: The next step is to multiply every digit of the multiplicand with every digit of the multiplier starting from the rightmost digit or the least significant bit (LSB). The product obtained after the multiplication of each digit of the multiplicand with the multiplier is called the partial product. Finally, we add the partial products obtained at each step using the rule of binary addition.

What is the Product of ($1111)_{2}$ and ($1111)_{2}$ Using Binary Multiplication?

The product of ($1111)_{2}$ and ($1111)_{2}$ using binary multiplication is ($11100001)_{2}$. In this binary multiplication, the multiplier and the multiplicand are the same binary numbers. We use the rules of binary multiplication, which are ' 0 × 0 = 0, 1 × 0 = 0, 0 × 1 = 0& and 1 × 1 = 1', and multiply the numbers as per the usual arithmetic multiplication method.

What is Binary Multiplication of Negative Numbers?

In the decimal or the base-10 number system, there are negative numbers, such as -1, -2, -3, and so on. It is possible to multiply a negative number with a positive number or a negative number with a negative number in binary, as well. To do this, we represent each number using 8 bits. In this, we use 4 bits to represent the number in 2's complement and 4 bits to represent the sign. If the sign of the number is positive then we use four zeros and if the number is negative then we use fours ones. 2's complement of a binary number is obtained by adding 1 to the one's complement of the binary number. 1's complement means reversing every 0 with a 1 and every 1 with a 0.