Multiplying Binary Integers

This is a very short explanation how binary integers are multiplyed.

Multiplying binary integers only uses shifting and addition. Let’s multiply two integers by hand to elaborate the algorithm. We will use 25 and 11, which are represented in binary as 11001 and 1011, respectively. This is the initial state of the algorithm:

11001 (25)
 1011 (11)

The following steps has to be performed:

Set the result to 0
Add the second integer to the result if the lowest bit of the first integer is 1
Shift the first integer to the left, which will discard its lowest bit
Shift the second integer to the right, which will multiply it by 2
Go back to step 2 if the first integer has any bits left

These are all the states:

       11001
        1011 -> +11

        1100 >>
    << 10110

         110 >>
   << 101100

          11 >>
  << 1011000 -> +88

           1 >>
 << 10110000 -> +176

           _ >>
<< 101100000

               = 275

The algorithm can be optimized if we use the smaller integer for right shifting. This is an implementation in C:

unsigned multiply(unsigned a, unsigned b) {
	unsigned c = 0;

	if (a < b) {
		unsigned t = a;
		a = b;
		b = t;
	}

	while (a) {
		if (a & 1) c += b;
		a >>= 1;
		b <<= 1;
	}

	return c;
}

The algorithm will also work with negative numbers. See a running example.

Other Links