Jump to content
Banner by ~ Ice Princess Silky
  • entries
    10
  • comments
    99
  • views
    2,268

Binary Math (Multiplication & SHL)


Splashee

687 views

Before we start with multiplication, it is important to understand that basically every CPU out there has a built in multiplication instruction. Why is this important? Well, because when I started doing research about Binary Math for my blog, I had very limited understanding of how multiplication and division worked, and while division is not supported by low end CPUs, multiplication is. And I can assure you that I cannot disassemble a CPU to figure out how multiplication is done!
The C and C++ standard requires the operations of addition, subtraction, multiplication, division, and modulo. If the CPU cannot provide any of them, they must be emulated and provided by the C/C++ compiler. That’s exactly what the compiler does for the CPUs that don’t support division. So after realizing how division is being emulated, I could figure out one way of doing multiplication! There are many ways of doing multiplication, and my take on it might not be the best. I am still proud I was able to work out a solution that gave the same results as the multiplication made by the CPU!

 

Knowing that multiplication can be done in a slow way, by just addition in a loop, there are still a few problems we need to concern ourselves with. The first one is obvious:

Make the loop count as small as possible. Loops are kind of slow on computers, because after a certain number of looped instructions, there must be a way of breaking out of the loop, and such a test requires the CPU to flush the cache. We must loop, so we must try to make the number of times (loop count) as small as possible. If we were to multiply 5 by 1000, then Adding 1000, five times is way faster than adding 5, athousand times. We need to find the factor that is smaller than the other factor. And we need to do this in Binary Math!

 

The second one might not be as obvious:

Deal with one or two factor(s) being negative number(s). As been seen in my previous blog about subtraction, negative numbers have their own rules to them. Adding a negative number is subtraction. How does that affect our multiplication product? Are there any specific rules that force us to not use negative numbers in the first place?

 

Dealing with negative numbers:

Learning from how division is dealt with, I simply know that it is possible, and best, to make the factors positive before calculating the product.
If one factor is negative, and the other factor is positive, the product will be negative. If both factors are negative, the product will be positive. Else, the product is positive.

 

First we must check if any or both factors are negative:

 

If the most significant bit of Factor 1 is 1, it is a negative number, so make it positive by doing a two’s complement operation on the number, and finally set a Flag to 1 to indicate a negative Product. Else, keep the Flag 0 to indicate a positive Product.

 

If the most significant bit of Factor 2 is 1, it is a negative number, so make it positive by doing a two’s complement operation on the number, and then do a bitwise NOT on the Flag to make it 1 if it was 0, or 0 if it was 1. The sign of the Product depends on the result of this Flag.

 

 

Dealing with factor size:

After we have only positive factors, we need to check their size. If either factor is 0, the product will be 0 (we should have done this before making the factors positive).

So the main problem is to check which factor is less than the other factor, as we want the loop count to be as small as possible. The loop count is the number of times we need to add the other factor with itself to get the product.

Factor 1 is less than Factor 2 if the difference between Factor 1 and Factor 2 is negative, else the difference is positive (or zero). Let’s say Factor 1 is 50 (110010) and Factor 2 is 49 (110001), and we are testing for Factor 1 being less than Factor 2:

 

First, prepare the subtraction by doing a two’s complement on Factor 2 to make it negative…

 

Invert each bit, and then add 1. This is explained in my previous blog entry about subtraction:

 

110001.

 

Bitwise NOT (invert bits):

001110.

 

Something went wrong here! Why do we still have a positive value? The most significant bit is 0 here, and it must be 1 to be a negative number. We have forgotten that in order to have negative numbers, we must have space for negative numbers. The highest number we can represent with 6 bits is 63, and half of that will be negative numbers if we treat the most significant bit as negative numbers. You can see that we already started out as a negative number before we started inverting the bits. I did this error on purpose, so that we are forced to understand negative numbers and not just how to calculate them! We need to extend the number of bits, so we can have negative numbers in the range of our example. This will work for now: Factor 1 is 50 (0110010) and Factor 2 is 49 (0110001). We only placed a zero in front of the binary numbers to make it work.
Let’s do the two’s complement on Factor 2 again:

 

0110001 (49).

 

Bitwise NOT (invert bits):

 

1001110 (-50).

 

And add 1:

 

1001111 (-49).

 

We have successfully done two’s complement, which made 49 negative (-49). Now we can add Factor 2 to Factor 1, and if the result is negative, Factor 1 is less than Factor 2:

 

x1111100

________

 0110010

+1001111

________

 0000001

 

(Note: We are only allowing for 7 digits, meaning the last carry stated here as an “x” is discarded! The number has passed the wrapping point, wrapped around and become a positive number, as a default part of Binary Subtraction. If this was not subtraction, the addition overflowed and the carry “x” tells us of that overflow!)

 

The result is positive, if the most significant bit is 0, which it is! That means Factor 2 is less or equal to Factor 1. This is a deliberate choice of mine to show what we need to do, to swap the factors around.

 

Swapping factors:

When we only deal with two binary numbers, they can be swapped (exchanging place with each other) by stepping through 3 Logical XOR operations. As I stated in my previous blog, Logical XOR is outside the scope of this blog (really, I tried to explain it, but it was more than I have currently written, so no).
So we could just say, Factor 1 is now Factor 2, while Factor 2 is now Factor 1, and problem solved.

 

But for the sake of clarity, I’ll show the step with assigning values as well:

Assign Factor 2 (49) to Temporary Factor (?).

Assign Factor 1 (50) to Factor 2 (49).
Assign Temporary Factor (49) to Factor 1 (50).
Result is Factor 1 (49) and Factor 2 (50), as they are now swapped!

The Temporary Factor is only used to remember Factor 2, as it is being overwritten by Factor 1 before it can be written to Factor 1.

 


 
Spoiler

 

And here is the swap using Logical XOR operations which requires no temporary storage, and is faster than anything I know of:

 
Logical XOR Factor 1 (50) with Factor 2 (49), equals Factor 2 (3).

Logical XOR Factor 2 (3) with Factor 1 (50), equals Factor 1 (49).

Logical XOR Factor 1 (49) with Factor 2 (3), equals Factor 21 (50).

Result is Factor 1 (49) and Factor 2 (50), as they are now swapped!

 


Looping though a factor:
As I stated before, multiplication is done by looping through the smaller factor, and adding the larger factor.
Well, it can be done that way, but binary works with power of 2 values. Instead of looping 49 times, we can choose to only loop 6 times instead. Why 6? Count the number of digits we must loop through, and it is made clear that the highest bit (furthest to the left hand side) that is 1 in the number 49 is located in the 6th digit: 0000000000000110001.
I added a lot of unnecessary zeros to show that the larger the number is, the bigger the loop count can become, but it is still far away from being as much as 49!

Adding to the product:
So we know we have to loop 6 times, but we don’t know what we need to add during each loop count. We are currently dealing with digit positions now, and their value, how much they are worth. We have already covered this in my first blog, about how to do addition and convert binary numbers to decimal numbers.
For each digit position, starting from the rightmost digit, the value is worth twice as much as the previous digit’s value to the right. Being at the very right, the value is worth 1. Meaning, the value of the digit to the left of that digit is worth 1 + 1 = 2. The next digit to the left is worth 2 + 2 = 4. Next is worth 4 + 4 = 8, etc.
The simplest form of multiplication is just to shift the digit from one position to the next, in the direction right to left. If you have the number 0001 which is worth 1, shifting that 1 bit two digits to the left, will make it worth 4 times as much: 0100 (4)!
Guess what, it works on any number! Imagine you have the number 5 (000101), and you shift it (all the bits) two digits to the left, will make it worth 4 times as much: 20 (010100)!

This is multiplication with a number that is a power of 2. However, it is not multiplication! We never multiplied anything. We just moved bits, from one digit to another digit, so called Bit Shifting. It is one of those bitwise operations, like Bitwise NOT. The name is actually Bitwise Shift Left. Or in short, Bitwise SHL.
The opposite of Bitwise SHL is Bitwise SHR (Bitwise Shift Right), and you would think it does the opposite as well, divide by a number that is a power of 2? You would be so close if you guessed YES! It is almost true, but it doesn’t work with negative numbers. And Binary Division doesn’t use it at all, as division also tracks the remainder. We’ll discuss Binary Division in my next blog entry.

 

So, we can multiply any binary number, including negative binary numbers by a number that is a power of 2, such as 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2084, 4096, 8192, etc. All we need to do is shift the bits to the left by as many steps required to reach the digit’s value.
But what if we need to multiple by a number that isn’t a power of 2?
Let’s say we want to multiply some number with the number 6. The number 6 is the sum of two power of 2 numbers:

4 and 2.

 

So if we have the number 1 (0001), and we want to multiply it with something to make it 4 (0100), all we needed to do was Bitwise SHL with 2. And the same goes if we have the number 1 (0001), and we want to multiply it with something to make it 2 (0010), all we have to do was Bitwise SHL with 1. If we then add the result of those shifts, we will get the number 6 (0110).
The important thing here is that we started out with the number 1 acting as the first factor. The two shift operations Bitwise SHL 2 and Bitwise SHL 1 acting as the second factor. And the sum of those shifts on the number is the product of the multiplication!

We did 1 * 6 = 6.

 

If we were to change 1 (first factor) into any other number, we would still multiply with 6 because of the two shift operations acting as the second factor. The question is: How do we find out how many shift operations we need? For 6 we needed two shift operations.
We have a partial answer in the loop count. The loop count for our factor 49 is 6, because that is the maximum digits we have to go through, to make up 49 inbinary. The other part of the answer comes from whether the digit is 1 or 0.

 

 

Adding shifted binary numbers to make the product:

So we start out with the Product being 0. For every loop in the loop count, we want to add a shifted factor. The question is, how much do we shift Factor 2 (50) before we add it to the Product? Well, every digit’s position in Factor 1 holds the answer, if the digit is 1. We need to shift Factor 2 (50) with the number of digit-positions where that 1 is located at, minus 1, because the first digit’s position shouldn’t be shifted (multiplied by 1, itself). Then, we add the result of that shift to the Product, and we do this until we have done 6 loops, or should I say 6 digits of Factor 1. And yes, if a digit from Factor 1 is 0, we do not shift and add anything!

 

 

 

Time for the looped action:

We have a loop count of 6, knowing that this is the maximum digits to process in Factor 1. We decide to do the digits right to left, even if it is possible to do them in the opposite direction. We start with the Product set to 0, and to help understand better, we do the examples where we shouldn’t, for clarity since shifting digits might be a new thing to you:

 

-Loop1 out of 6:
Check the 1st digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
Shift Factor 2 with the number that represents the 1st digit’s position, minus 1. This means we will shift by the number 0, which isn’t a shift at all!

Add to the Product (0), Factor 2 (0110010) Bitwise SHL with 0, which is still (0110010).

The Product is now 50  (0110010). Go to the next loop

 

-Loop2 out of 6:
Check the 2nd digit in Factor 1 (0110001) if that digit is 1, else go to the next loop
Shift Factor 2 with the number that represents the 2nd digit’s position, minus 1. This means we will shift by the number 1:

Add to the Product (50), Factor 2 (0110010) Bitwise SHL with 1, which is (01100100).

Product is now 150  (010010110). Go to the next loop…

 

-Loop3 out of 6:
Check the 3rd digit in Factor 1 (0110001) if that digit is 1, else go to the next loop
Shift Factor 2 with the number that represents the 3rd digit’s position, minus 1. This means we will shift by the number 2:

Add to the Product (150), Factor 2 (0110010) Bitwise SHL with 2, which is (011001000).

The Product is now 350  (0101011110). Go to the next loop…

 

-Loop4 out of 6:
Check the 4th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop
Shift Factor 2 with the number that represents the 4th digit’s position, minus 1. This means we will shift by the number 3:

Add to the Product (350), Factor 2 (0110010) Bitwise SHL with 3, which is (0110010000).

The Product is now 750  (01011101110). Go to the next loop…

 

-Loop5 out of 6:
Check the 5th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
Shift Factor 2 with the number that represents the 5th digit’s position, minus 1. This means we will shift by the number 4:


Add to the Product (50) <Note: We arrive here from Loop 1>, Factor 2 (0110010) Bitwise SHL with 4, which is (01100100000).

The Product is now 850  (01101010010). Go to the next loop

 

-Loop6 out of 6:
Check the 6th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
Shift Factor 2 with the number that represents the 6th digit’s position, minus 1. This means we will shift by the number 5:


Add to the Product (850), Factor 2 (0110010) Bitwise SHL with 5, which is (011001000000).

The Product is now 2450  (0100110010010). And the loop is completed!

 

 

We did 50 * 49 = 2450.

 

 

But, don’t forget to check the Flag at the end! If the Flag was set to 1, it means the Product should be negative, because one of the factors was a negative number. A two’s complement operation on the Product will make it negative.

 

And that is Binary Multiplication!

  • Brohoof 4

6 Comments


Recommended Comments

So, it's the same way that multiplication is done on paper (with the exception of additional operations for negative numbers). Some CPUs have dedicated circuits for that instead of taking many cycles to multiply.

  • Brohoof 1
Link to comment
4 minutes ago, Pentium100 said:

So, it's the same way that multiplication is done on paper...

Well, this is completely my take on it. I have only seen constant written multiplies before (no loop, just a sequence of shifts and adds).

 

Here is my "tested and working" C code for the multiply, which might be easier to understand than my explanations:
 

signed long NumLeadingZeroes(signed long arg)
{
	int i;
	for (i = 0; i < 32; i++)
	{
		if (arg & 0x80000000)
		{
			return i;
		}

		arg <<= 1;
	}

	return 32;
}

signed long splashee_multiply(signed long factor1, signed long factor2)
{
	signed long product = 0;
	unsigned long pos, mask;

	int factor_sign = 0;

	if (factor1 == 0 || 
		factor2 == 0)
	{
		return 0;
	}

	if (factor1 < 0)
	{
		factor_sign = 1;
		factor1 = -factor1;
	}

	if (factor2 < 0)
	{
		factor_sign ^= 1;
		factor2 = -factor2;
	}

	if (factor1 > factor2)
	{
		factor2 ^= factor1;
		factor1 ^= factor2;
		factor2 ^= factor1;
	}

	pos = 31 - NumLeadingZeroes(factor1);
	mask = (1 << pos);

	do
	{
		if (factor1 & mask)
		{
			product += (factor2 << pos);
		}

		--pos;
		mask >>= 1;
	}
	while (mask);

	if (factor_sign)
	{
		product = -product;
	}

	return product;
}

 

Link to comment

Well, that is how it is done on paper:

1234 x 5678 in decimal of course.

    1234
    5678
--------
    9872  (1234 * 8)
   8638.  (1234 * 7 << 1)
  7404..  (1234 * 6 << 2)
 6170...  (1234 * 5 << 3)
--------
9872+86380+740400+6170000=7006652

There should be zeroes in place of the dots, but normally they are not written. They are used when adding the total product.

Edited by Pentium100
  • Brohoof 1
Link to comment

I read everything and it is very interesting :wau:

Edited by Muffinnz
  • Brohoof 1
Link to comment
On 4/6/2020 at 11:39 PM, Muffinnz said:

I read everything and it is very interesting :wau:

Cool!

It has been some time since I worked with binary math, however, I am currently working with compression, which involves trying to remember binary bits, but make the size of data smaller than the original. Quite challenging!

 

21 hours ago, Jesse Terrence said:

It's june. Will there be another blog on computer maths?

I wish. The next one is division, and it is still a little bit odd. Requires me to try to understand a few crazy things.

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Join the herd!

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...