Binary arithmetic

Now we have a general understanding of how data is organized in a computer’s memory. However, such knowledge is entirely useless, unless we know how to handle data in binary form. In other words, there is no good in numbers if you do not know how to add/subtract/etc.

It is where Boolean[6] algebra enters the scene. Boolean algebra naturally operates on values 1 and 0 (true and false), which perfectly fits our needs, and provides all the tools needed for arithmetic operations on binary numbers (that is why it is fundamental in computing and digital electronics). If we attempt to emulate Boolean algebra with regular arithmetic, we will perform all computations on 1’s, and 0’s only, divide the resulting value by 2 and take the quotient as the final result. Such arithmetic is called integer arithmetic modulo 2 (or GF(2)[7]). However, it is important to mention that there is no such thing as addition/subtraction/etc. in Boolean algebra, at least not as we know it, instead, it uses Boolean operators (or gates in digital electronics).

There is a limited set of four basic[8] operators:

·         NOT – inverts the given value (NOT 1 = 0).

·         OR – “returns” the maximum of two values (0 OR 0 = 0, 1 OR 0 = 1).

·         AND – “returns” the minimum of two values (1 AND 1 = 1, 1 AND 0 = 0).

·         XOR – exclusive OR, “returns” 1 only if two values are different (1 XOR 1 = 0, 1 XOR 0 = 1).

The word “returns” is quoted because operators are not functions, they do not return values, they operate on them instead. The following four truth tables show the exact behavior of each of the basic operators depending on the input values.

Table 4.    Truth tables for basic Boolean operators

Binary addition

These truth tables, however, do not provide any explanation on how binary arithmetic works. All we know is that when we add two bits like this (1 + 0) mod 2 the result would be 1, just like in ordinary arithmetic, but, if we add 1 to 1, shouldn’t the resulting value be 2? The answer is no, at least not in case of addition of two one-bit values. Instead, we need some mechanism for detection of “lost” bit and that is when Boolean AND comes to our aid.

Suppose we have to values A and B that we want to add. Each value is exactly one bit, and each of them equals 1. Before we proceed, it is the perfect time to introduce the carry. Carry is a digit that is transferred from one column of digits to another column of more significant digits (Wikipedia) and, to put it in simple words, we ran out of digits. For now, as we have no column of more significant bits, we would be satisfied by merely knowing whether carry occurs or not.

As in binary arithmetic addition is performed by XOR operator we simply use it to add A to B (remember A = 1 and B = 1):

1 XOR 1 = 0

Then we use AND operator to check whether carry occurs:

1 AND 1 = 1

The result equals 1, meaning that carry occurred.

Now it looks like we are mature enough to try a few more bits, for example, 4. How about we add 9 to 7? This time we will be using a table to make the case more illustrative.

As we see, the first bits of A and B are equal to 1. Therefore all is simple, and we just perform the same procedure as in the previous example:  Result = 1 XOR 1 = 0 and Carry = 1 AND 1 = 1. Do not forget to move the carry to the next column (the 2¹ one).

The situation is a bit different for the second and the rest of bits as we do not merely add second bit from A to second bit from B, but add the carry bit too: Result = (0 XOR 1) XOR 1 = 0 and carry would be (0 XOR 1) AND 1 = 1. The table will look like this:

We proceed and perform the same procedure for the third bit and get:

And the last time:

The result equals to 0 despite the fact that 9 + 7 = 16 or 1001b + 0111b = 10000b. As we see the result would be five bits long, but as we only have four bits for each variable in this example, the would-be most significant bit remains as a carry (we will see how such situation is handled in the next chapter).

Binary subtraction

Before we proceed to binary subtraction, we have to understand how signed and unsigned numbers are implemented in binary arithmetic. In binary notation, the sign of a signed value is indicated by the most significant bit, where 1 denotes a negative value and 0 denotes a positive one. However, setting the most significant bit to 1 is not enough to convert a positive value to negative. For example, if we want to convert a byte value of 1, which would be represented as 00000001b, to -1 and simply set the most significant bit to 1, we would get 10000001b as the result which is -127, while negative 1 would be represented by 11111111b. To understand how this happens, let us inspect the process of negation of a binary number, which is called two’s complement. To change the sign of a number we have to invert its bits first, which in case of 00000001b would result in 11111110b, and then add 1. The final result would be 11111111b (the most significant bit set to 1 denoting a negative value).

Let’s see how binary subtraction works by example. Suppose we have two bytes A and B, where A = 01110010b (0x72) and B = 01010011b (0x53) and we want to subtract B from A. We, of course, may perform the subtraction by means of regular arithmetic, but our intention is to see how it works with Boolean operators on a bit per bit level. Just remember to add bits and calculate carry bit with the previously mentioned formulae using XOR and AND operators.

·                     The first step would be an inversion of all bits of byte B:
NOT 01010011b = 10101100b;

·                     Complete the two’s complement by adding 1 to the result of step one (remember to perform the calculations from right to left):

3.      Add the resulting 10101101b to byte A:

The result is 00011111b (0x1F). Notice the carry bit – its presence means that we were subtracting a smaller integer from bigger one and no borrow[9] has occurred. Let’s try to subtract A from B to make this example even more illustrative.

·                     The first step would be an inversion of all bits of byte A:
NOT 01110010b = 10001101b;

·                     Complete the two’s complement by adding 1 to the result of step one (remember to perform the calculations from right to left):

3.      Add the resulting 10001110b to byte B:

The result is 11100001b, which, if treated as a signed value, is a negative number and the fact that carry bit equals to 0 denotes an occurred borrow.

It is important to note the fact that a number may be signed or unsigned within a specific range of bits, but that is only an abstraction which is essential for us and the compiler, while the processor is unaware of sign as a concept at all, although, it provides us with specific indications of sign, sign change, etc.

Binary multiplication

Binary multiplication, just as any other multiplication, is merely an iterative addition. While the idea behind multiplication is the same, there are several ways of implementation. However, since our goal is to obtain a general understanding of how multiplication is performed on a binary level, we will not dive into technological aspects or other, more complicated, but more efficient algorithms.

What we do in decimal worlds is we multiply the multiplicand by each digit of the multiplier writing down products in the column, while shifting each next product to the position of the digit we multiplied by. For example, 127 * 32 would be (decimal notation):

Here we first multiplied 127 by 32 getting 254, then multiplied 127 by 3 getting 381, but, since it is multiplication by 30 rather than by 3, we shifted 381 one digit to the left or multiplied it by 10. The final step was the addition of the two products.

The same multiplication rule applies to binary multiplication with only one additional aspect to keep in mind – we should use Boolean operators to better understand how the process flows in a processor. As usual, we will be operating on eight-bit bytes.

Suppose we have two bytes - A=01110010b and B=00000101b (0x72 and 0x05 respectively), and we want to multiply A by B:

Table 5.    Long multiplication of binary numbers (Gray zeros represent shift amount).

As we see, we have to first multiply 01110010b by the first bit of B, which in Boolean representation is applying AND operator to each bit of A and the first bit of B. In the second step we do the same for the second bit of B and so on, up to the last bit of B. This example also introduces the fact that the product is always twice the size of multiplicand (and the size of multiplier is the size of multiplicand), which, in case of 8-bit multiplicand is 16 bit – 0000001000111010b.

Binary division

Binary division follows the same algorithm of the long division as decimal numbers, and it all comes down to iterative subtraction of divisor from portions of the dividend. The following example fully illustrates the process.

Suppose we have two bytes A and B, where A=11010011b and B=00001100b, and we want to divide A by B. The first step we should take is to align the two values by their most significant bits and the alignment is performed by shifting left the divisor as needed. In our case, we shift the divisor 4 bits to the left B << 4 = 11000000b (grayed out bits represent the shift amount and do not participate in the further calculation process) so that we have:

A=11010011b
B=11000000b

Then we subtract B from the corresponding bits of A, meaning 1101b – 1100b, which results in 0001b. As this intermediate result fits the condition of being above or equal to 0, we write 1 to quotient while the intermediate result becomes new dividend.

Now we have to align the most significant bits of the dividend and the divisor, but this time, instead of shifting the divisor, we start borrowing bits from the original dividend and append bit at position 3 in the initial dividend to our intermediate result getting 10b. However, since subtracting 1100b from 10b would result in a negative number, we append 0 to the quotient and borrow the next bit at position 2. Having 100b we would still get a negative number after subtraction, so we append 0 to the quotient and borrow the next bit at position 1. We will return on these steps until we can either subtract our divisor from the intermediate result or get a positive value or 0, or we run out of bits in the original dividend (in which case, the intermediate result is the remainder).

In this particular example, we will have to borrow all the remaining bits from the original dividend to be able to subtract 1100b and get a positive result. In the end, we would have 10001b as the quotient and 111b as the remainder.

11010011|1100 ß divisor
1100    |10001 ß quotient
   10011
    1100
     111 ß remainder

Grayed out bits in the intermediate result represent bits “borrowed” from the original dividend.