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

Binary Math (Subtraction & Negate)

Splashee

Entry posted by Splashee

717 views

 Share

This is a follow up to the previous blog entry (read it first to understand Binary numbers):
 

Spoiler

 

 

Subtracting two binary numbers is as easy as adding two binary numbers. In fact, it is the same.
Computers deal with bits, and the number of bits are limited. The smallest number of bits that the computer can access is 8 bits, called a "BYTE" (a wordplay of "by eight"). 8 bits can contain 256 different bit pattern combinations, and that gives us the total numbers we can count using binary math with 8 bits. The origin of 8 bits is actually tied to characters, in order to store letters (to emulate old type writers).
We are however still bound to 256 different bit patterns, when we want to include negative numbers.

Binary numbers wrap around. The bit patterns keep repeating even when we run out of bits. That means that if we are on the number 255 and we add 1, we will end up on 0. And if we are on 0 and subtract 1, we will end up on 255 again. Note that 255 in this case is positive! Also note that we subtract decimal numbers here, not binary numbers.

With a limited number of bits available, it is easier for the computer to simply ignore the subtraction operation for binary numbers as it is the same result to add a negative number as it is to subtract a positive number.

 

An example:
9 - 5 = 4 (subtraction)
9 + -5 = 4 (addition)

 

Without subtraction, the computer doesn't need to "borrow" digits. Instead, digits can be "carried" using addition instead. One system to deal with two operations, is simply smarter. Subtraction can then be disguised behind the scenes as addition with negative numbers.

 

But we still need to know what a negative number is. We need to have a way to identify a negative number from a positive number. And we need negative numbers to be lower than positive numbers, so that we can "move backwards" in the bit patterns that the binary numbers represent.
Remember how I told you earlier that binary numbers wrap around? It is the wrap around that makes the magic possible, and allows us to do math in the reverse direction. By adding a large number to our current number, it will most likely wrap around. Adding for example 256 to any number in a BYTE would equal the same number before the addition took place, since a BYTE can only store 256 unique bit patterns. The previous statement has a huge error in it, and that is, we cannot add 256 since the largest number we can represent in a BYTE is 255. If we go by BYTE size numbers, that is. I said 256 unique bit patterns, and if you think about it, one of them is 0. Since binary numbers wrap around, adding 1 to 255 should in fact give us 256, however it gives 0. And I also said if we could add 256 to any number, that would give us the same number, and adding 0 to any number would do the same thing. So 256 and 0 is the same number in the world of wrapping.
Wrapping around can be a serious headache. But it has the solution to our problem:

If we can only represent any number between (and including) 0 to 255. Then adding 255 to any number of our choosing, will wrap around the result to our number minus 1. We have a way to do subtraction by 1.
So what is 255 then? The numbers wrap around so if we subtract 1 from 0, we will end on 255. That means, 255 must be equal to -1. Let's just stop here, and say that the value 255 can be both 255 and -1. Because that is the truth. Wrapping is a pain to understand, and we need to see it to believe it. So let's get down to the basics. In a world of BYTEs, where nothing can be smaller, binary numbers can be smaller, and they can wrap around at other values than 256, such as 128, 64, 32, 16, 8, and 2.

 

Let's choose the wrap around to be 16. By doing that, we can in the most easiest way see how wrapping works including representing both positive numbers and negative numbers.
We draw a circle, like an analog clock (read it clockwise). It has bars to represent each number, 16 in total. In the outer part of the circle, we name each bar with a positive decimal number, as well as the binary number limited to 4 digits (4 bits). The inner part of the circle has the positive and negative decimal numbers, if we chose to represent the binary numbers as signed numbers:
signed_chart.jpg

At the top of the outer part of the circle, the bar is named 0. It is the wrapping point, as the numbers wrap around there. 16 and 0 are the same number, only we cannot represent 16 in a binary number with only 4 digits. Standing on 15, and adding (moving clockwise by) 1, will end up on 0. And standing on 0, and subtracting (moving counter clockwise by) 1, will end up on 15. You can also see that 15 is represented as -1 by reading the inner part of the circle.
Another thing to notice is that half of the circle seems to be on the negative number side, and the other half on the positive number side. There are actually the exact same number of negative numbers as there are positive numbers, if you count 0 as a positive number.

 

Let's dive deeper into this half circle. Look at the bit patterns of the blue numbers, the binary numbers limited to 4 digits. Notice the leftmost digit is 0 if the number is positive? And it is 1 if it is negative? This digit, or bit, has a name: "Most Significant Bit". It is the minus sign, telling us that the number is a negative number. If we want to play with negative numbers, then we can simply make a number negative by turning the leftmost digit from 0 to 1, making it act as a minus sign. That will tell us that the number is negative, however, it will not make the current number into its negative form. Here is an example, if you have the number 3, and want to make it negative, turning on the leftmost bit will yield the number -5. You can see it if you look at the blue binary numbers in the circle! We cannot negate a number without a specific formula.

 

If we want -3 from 3, or 3 from -3, a negate operation, we cannot just add a number. We need to do an operation known as two's complement.
Two's complement works on any binary number, no matter how many digits there are to represent the number. We don't need to think about the wrapping point. We only need addition, and an operation known as bitwise NOT. (In computer logic, both addition and bitwise NOT are done using a bitwise XOR on finite bit numbers. XOR is outside the scope of this blog entry!)

If you have a binary number, you can easily do a bitwise NOT by stepping through each digit, and swap the digit from either 0 to 1, or 1 to 0. All the bits in the binary number will become inverted. If you invert something twice, it becomes the same value again. Let's try it on a really long and unknown binary number:

10010100100101010101001010101101111110001

Inverted using bitwise NOT:

01101011011010101010110101010010000001110

And invert it again using bitwise NOT will yield the original number:

10010100100101010101001010101101111110001

 

So, if you have 3, and you want -3. First represent 3 as its binary number:

0011

Invert each bit (using bitwise NOT):

1100

Now add 1, and you will end up on -3:

1101

Confirm with the circle above!

 

 

So, we should be able to do the same with -3, to get 3. Let's do the same two's complement to prove that it works:

1101

Invert each bit (using bitwise NOT):

0010

Now add 1, and you will end up on 3:

0011

Confirm with the circle above!

 

Yes, this is done with 4 digits, so that we can draw a circle with only 16 steps, and get a nice amount of positive and negative numbers, in order to learn wrapping and two's complement.
But how do we subtract a number then?

 

This is where you have to read the first blog entry (see the top for a link), for how you do addition with binary numbers. All you need to do is add a number that is negative, to subtract. It is that simple!
And how do you get a negative number? With two's complement.

 

 

 

 

This is the end of this blog, however, as a game programmer, I am using wrapping all the time...
 

Spoiler

If you program in a language that is similar to C (C++), you might have done something similar to this, to check if a number is inside -8 and (including) 7: 


if (number >= -8
    &&
    number < 8)
{
    // Is inside -8 and (including) 7
}

The variable number can be negative, and any integer (whole number) value. But the issue here is not what it can be, but how we are forced to check it twice! We have to check if the value is higher or equal to a negative value, and at the same time also check if that same value is less than a positive value.

As I said in the blog, you can represent a binary number as either negative or positive. Such that (in case of 8 bits numbers) the value -8 and 248 are the same number. We know that 248 is higher than 8. And we are already checking if the variable is less than 8.

By reading the variable number temporarily interpreting it as an unsigned value (a BYTE that can only be positive), we can do type casting which is part of the C programming language to produce this single check, which is equal to the one above, only *faster since it requires only one check instead of two checks:
  


if ((unsigned)(number + 8) < (unsigned)(8 + 8))
{
     // Is inside -8 and (including) 7
}

What happens here, is that we move the value of number temporary into unsigned space (wrapping the value around if necessary), making any value that was -8 and above into 0 and above instead. If the value of number was -9, it would end up as -1, but the check is done on an unsigned value, meaning the value (if it is a BYTE) would be 255 instead of -1, which is definitely higher than (8 + 8). One check instead of two. We remove negative numbers, and we depend on binary numbers wrapping around.

 

*Note "faster": We are adding twice here, but 8 + 8 is compiled into an immediate constant 16 by the C compiler, and number + 8 is faster than one extra check since a check requires a jump/branch which forces the CPU to flush its cache.

 

Next up in the blog, we have Binary Multiply... (See you next time!)

  • Brohoof 4
 Share

13 Comments

Recommended Comments

Pentium100

You talk about how wrapping around is such a difficult concept, but this happens with decimal numbers as well. 

Take a look at an odometer from a car:

Image result for w123 odometer

 

Once it reaches 999999km (or the bottom one to 999.9km), driving one more km (or 100m) makes it go to zero, because there are not enough digits in the counter. Binary numbers wrapping work exactly the same.

  • Brohoof 2
Link to comment
Splashee
9 hours ago, Pentium100 said:

You talk about how wrapping around is such a difficult concept, but this happens with decimal numbers as well.

I would think that doing math with wrapping decimal numbers would be quite more difficult. Decimal numbers keeps going forever, and applying wrapping does things that (at least I) cannot be used.

The concept is difficult because it is used all the time in binary, to do operations that are not really applicable on decimal numbers. Like the Most Significant Bit representing the minus sign, is required to be the bit before the wrap around, no matter how many digits the binary number has, because it is required to act as the negative side (below zero).

I am using wrapping in my game programming, to find the shortest distance between two objects, in wrapped space, where both objects are in absolute space (much farther away from each other, one might even be on the negative side). They might be so far away, but in the game they are only 3 units apart, because they both wrapped around so many times in different directions, they ended up close to each other in wrapped space. That kind of math even failed in the original Sonic games as well as in New Super Mario Bros, and those programmers have more experience than me for sure.

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

Decimal numbers keeps going forever, and applying wrapping does things that (at least I) cannot be used.

So do binary numbers. The difference is that the way binary numbers are used in PCs is fixed-length variables, just like the mechanical counter with fixed number of wheels. Just like the mechanical counter with 3 wheels wraps around at 999+1 (because there is no fourth wheel), a 3 bit binary variable wraps around at 111+1 (because there is no fourth bit).

If I set the three wheel odometer to zero and drive 1500km, the odometer will show 500. Just like your wrapped space. If I did not notice it going to 999, I could just say that I drove 500km. This means that if I manage to drive my car 1100000km, the odometer would only show 100000 and it would be perfectly legal because I did not tamper with it.

56 minutes ago, Splashee said:

Like the Most Significant Bit representing the minus sign, is required to be the bit before the wrap around, no matter how many digits the binary number has, because it is required to act as the negative side (below zero).

And if you want to convert a signed 8bit integer to a signed 16bit integer, you need to pad the most significant bits of the bigger variable with the most significant bit of the smaller one.

Edited by Pentium100
  • Brohoof 2
Link to comment
Brony Number 42

@Pentium100 is there something like bitwise NOT for something other than binary? I see how it works on bin, but can we have something similar with dec? Is there a dec compliment? Modular arithmetic perhaps?

  • Brohoof 1
Link to comment
Splashee
1 hour ago, Brony Number 42 said:

@Pentium100 is there something like bitwise NOT for something other than binary? I see how it works on bin, but can we have something similar with dec? Is there a dec compliment? Modular arithmetic perhaps?

This is kinda what I want to know as well.

On paper, we just add a minus in front of a number to make it negative. Even calculators do bitwise NOT and then add 1 (two's complement) to make a decimal negative (the +/- button), since the values are binary converted to display decimal.

 

I will go more into detail on wrapping when we get to Binary division.

 

The situation with binary is that you can wrap a number by 2, meaning you can find odd and even numbers. Again, we can do the same in decimal, but the cost is high! I will cover that in Binary division.

 

Let's say, we have a decimal number, 9999, and it wraps around at 10000, so 9999 + 1 becomes 0000. What if we define 9000 to be the sign, so the last "9" is a negative sign. But if we did a circle like before, half of the numbers should be positive and the other half negative. That means 5000 positive (including 0 as positive) and 5000 negative, but wouldn't 5000 be the sign bit then? What is it I am missing? What makes binary so good (or bad) at doing this, compared to decimal?

Also, @Pentium100, if you drive your car backwards, and you started from 0 (this is important, as you must go negative), by math alone, you would go a negative distance. The odometer display might not show that as negative, or even update (because of special case rules, again making mathematics really difficult), but it would wrap around to the highest number if it could count backwards, however the math doesn't work that way (negative_number modulo wrapping_point equals negative_remainder_that_if_made_absolute_is_mirrored)! But if the car has driven backwards over the wrap point, and it just happened to be 0 to negative (basically any relative distance calculation), the mathematics forces us to get a negative remainder that is in reverse, breaking the entire system that wrapping depends on (everything gets mirrored). I'll cover this is Binary division, to make it fully clear.

 

I am sure there must be a solution to wrapping and negative with decimal numbers (without emulating them in binary numbers), and i am looking forward to go though every aspect of it!

  • Brohoof 1
Link to comment
Pentium100

This is the same with binary and decimal:

000 - 1 = 999 (decimal)
000 - 1 = 111 (binary)

So that part works. The difference is how we can define negative numbers in our decimal "computer" (though I wonder how they did this in actual decimal-based computers, but most of those were still kind-of binary, like BCD).

Anyway, let's try. If we copy from the binary version, we should define somewhere near the midpoint as the line between positive and negative numbers. Let's say that 499 = +499, 500 = -500, 599 = -401, 999 = -1. Sign indicator is the first digit. If it's >=5, it means that the number is negative.

Adding numbers works OK. 100 + 1 = 101, 998 (-2) + 1 = 999 (-1).

To negate a number you need to subtract it from 1000 (1000 - 1 = 999). You can also do it, like in binary, by manipulating each digit wheel separately. You need to set it to 9-current_value, for example (9->0; 8->1; 0->9 and so on) and then add one. Let's try negating some numbers:

001 -> 998 +1 = 999
400 -> 599 + 1 = 600
499 -> 500 + 1 = 501
000 -> 999 +1 = 000
To get a positive value from negative you need to subtract one and then turn the wheel to 9-current_value:
999 -> 999 -1 -> 998 -> 001
501 -> 501 -1 -> 500 -> 499
500 -> 500 -1 -> 499 -> 500

Seems to work. The special cases (0 and -500) turn into themselves, but it's similar to binary as well, since there is no positive number available.

Edited by Pentium100
  • Brohoof 2
Link to comment
Splashee

We need to keep the same operation to negate (two's complement is the same operation for both positive and negative numbers):

 

400 -> 599 + 1 = 600
600 -> 399 + 1 = 400 (it worked, thank god!)

 

499 -> 500 + 1 = 501
501 -> 498 + 1 = 499 (worked again)

 

Great job @Pentium100 :darling:

  • Brohoof 1
Link to comment
Pentium100

And it all started by me wishing to show that overflow is not such foreign concept and not exclusive to computers, but is common to all fixed-length counters and such..

  • Brohoof 2
Link to comment
Splashee

@Pentium100 Yea, overflows are very important to detect.

CPUs usually have an overflow flag (a bit in the flag register), a carry flag (to be able to so arithmetic on multiple bytes, remembering the previous carry), a parity flag (I wonder what purpose to use that one?), and of course the important zero flag (for checking equal conditions).

 

There are situations where I think an overflow wouldn't be detectable. Looking at source code for certain assembler instructions, makes me see how they check for overflows, and it seems if the value wraps around, there wouldn't be a way to check for overflow... But I might be wrong.

  • Brohoof 1
Link to comment
Pentium100
Just now, Splashee said:

a parity flag (I wonder what purpose to use that one?)

So that you can have the parity without calculating it separately, for example, if you want to transmit data on RS-232, you may use parity to detect errors (it's not really used , for some reason the settings are always 8n1, but you can have parity). Parity is rather difficult to calculate (you would probably need a loop for that or a lookup table), but easy to implement in hardware (a few XOR gates). However, it seems that the parity flag in x86 is also used for other purposes than just showing the actual parity. 

Overflow bit in a CPU is essentially the 9th (or whatever) bit of the register, when the register goes from 255 to 0 by adding one, the overflow bit is set (and in theory you could use the overflow bit to kinda-have a slightly bigger register).  

0|11111111
+
0|11111111
----------
1|11111110

the bit before the pipe is the overflow bit.

  • Brohoof 2
Link to comment
Splashee

Cool!

 

Yea, I have ran into the parity flag before, hidden deep inside MS-DOS 7 code that decrypts the splash screen logo. The meaning of it was different though, like you said. It is being used for other things.

 

So if the overflow bit is not set, but you still had an overflow, that could happen right? 

        11111111
    mul 11111111
      __________
1111111000000001
       -

Multiplying, gives 0 at that digit. The overflow much work differently, or not at all?

Edited by Splashee
  • Brohoof 1
Link to comment
Pentium100

On x86 the output of MUL is in two registers instead of one, so it's double the width. 
Same with 8051 (an 8bit CPU) - the result of MUL of two 8bit registers is stored in two 8bit registers.
On both x86 and 8051, overflow flag indicates if the result would fit in one register, if it's set, you need to handle both result registers.

255*255=65025, so the result will always fit in two registers.

Edited by Pentium100
  • Brohoof 2
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...