Binary Math (Subtraction & Negate)
Entry posted by Splashee
865 views
This is a follow up to the previous blog entry (read it first to understand Binary numbers):
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:
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...
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!)
-
4
13 Comments
Recommended Comments
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