Binary Arithmetic

Warning

In this section we are no longer dealing with Boolean Algebra. Binary addition gives different results than Boolean addition (the OR operation), so it is important to understand the distinction.

Binary Addition

Binary addition works just like regular addition you are used to in the decimal system.

\[0 + 0 = 0\]

\[1 + 0 = 0 + 1 = 1\]

\[1 + 1 = 10 = 0 + \text{carry bit}\]

\[1 + 1 + 1 = 11 = 1 + \text{carry bit}\]

Here is an example where any carry bits in each column are shown by superscript 1s. The addition is done column by column, starting with the LSB column.

Example of binary addition

  ¹011    (3)
+  110    (6)
------
  1001    (9)

Concept Check: Try the addition yourself.

  1001
+ 1111
--------

Solution

  1001
+ 1111
--------
 11000

Binary Subtraction

Subtracting a number is the same as adding a negative number. How could we represent negative numbers in binary?

A naive method would be to add one extra bit that represents the sign. For example, we could have a convention that a 1 in front means the number is negative, and 0 positive. For example 00011 would be \(+3_{10}\), and 10011 would be \(-3_{10}\). Although simple to understand, this system is terrible because adding the numbers together will give the wrong result.

For example:

  00011    (+3)
+ 10011    (−3)
-------
  10110    (−6) ≠ 0 

A much better system and one used nearly universally to represent negative numbers in binary is known as the 2’s complement system. In this system, the first bit is still a sign bit, but how the rest of the bits represent the number will take some explanation. The good news is that positive numbers in this system are the same as you are used to, just with a leading zero to show they are positive. So, in a 4-bit system 0101 would be +5. But now with this system, -5 is 1011, which is not so intuitive. 1011 is said to be the 2’s complement of 0101. How did we get this? We will first start by explaining how to calculate a number’s 2’s complement, then we will go back and explore why it is a good representation of a negative number.

To obtain the 2’s complement of a binary number, first start by inverting every bit so that ones become zeros and vice versa. (This is known as the 1’s complement). Then, add 1.

Example

Find the 2’s complement of 101101.

101101  →  010010    (1's complement)
         +      1
         --------
           010011    (2's complement)

The 2’s complement of 101101 is 010011.

Exercise:

What is the 2’s complement of \(13_{10}\)? (i.e. \(-13_{10}\))

Solution

First we need to think of how many bits we will need to represent \(13_{10}\). This is less than \(16_{10}\) so normally we would only need 4 bits. But because the 2’s complement system has a sign bit, we will need 5 bits total.

So +13 in a 5-bit system is 01101.

Then to find the 2’s complement, we flip all the bits and add one.

01101  →  10010    (1's complement)
        +     1
        -------
          10011    (2's complement) = −13

Let’s double check that addition works in this system.

     01101  (+13)
+    10011  (-13)
  --------
 [1] 00000  (0)
  └→ overflow bit is ignored
     we will talk about this more

So why does this system work? To guide us, let’s explicitly write all the 4-bit numbers in a table.

Binary Representation	Unsigned Decimal Equiv.	2’s Complement Decimal Equiv.
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	−8
1001	9	−7
1010	10	−6
1011	11	−5
1100	12	−4
1101	13	−3
1110	14	−2
1111	15	−1

Examine the \(\pm x\) pairs. Do you see the pattern? What is \(1 + 15\)? \(4 + 12\)? \(10 + 6\)?

The sum of each number with its 2’s complement negative counterpart equals 16 in the unsigned representation. This leads us to why the 2’s complement system works. It uses modular arithmetic!

As stated before, modular arithmetic means every multiple of the base is 0. In the above example, the base is 16, and in general will be \(2^N\) for an N-bit number. Since, for example, \(10 + 6 = 16 = 0 \bmod 16\), we can instead represent 10 as the additive inverse of 6, which is −6. We say that 10 is congruent with \(-6 \bmod 16\), since adding 10 to any number will be the same as subtracting 6.

Here is one example showing that in a mod-16 system adding ten is the same as subtracting six.

\(12 + 10 = 22 = 6 \bmod 16\) since \(16 + 6 = 22\). And, obviously, \(12 - 6 = 6\).

In the 2’s complement system each number staring with a 1 (that is, greater than \(2^{N-1} - 1\)) is replaced with its congruent additive inverse modulo base \(2^N\).

---

Here is a formal proof that taking the 2’s complement of an N-bit number gives the additive inverse modulo \(2^N\).

First, note that \(1 - x = \bar{x}\) for any \(x\) in binary.

i.e. \(1 - 0 = 1\) and \(1 - 1 = 0\).

This means that finding the 1’s complement (flipping the bits) of an N-bit binary number is the same as evaluating \(2^N - 1 - x\). For example:

\[\begin{split}\begin{aligned} & \; 1111 && (2^4 - 1) \\ - & \; x_3 x_2 x_1 x_0 && (x \text{ – a 4-bit #}) \\ \hline & \; \bar{x}_3 \bar{x}_2 \bar{x}_1 \bar{x}_0 && (\text{1's complement of } x) \end{aligned}\end{split}\]

Now, to simplify notation I will refer to taking the 2’s complement of \(x\) as \(TC(x)\) and 1’s complement as \(OC(x)\).

We need to prove that:

\[x + TC(x) = 0 \bmod 2^N\]

\[\begin{split}\begin{aligned} \text{LHS} &= x + TC(x) \\ &= x + OC(x) + 1 && \text{from our def'n of the TC procedure} \\ &= x + 2^N - 1 - x + 1 && \text{from our note above} \\ &= 2^N \\ &\equiv 0 \bmod 2^N && \text{since } 2^N \text{ is clearly a multiple of } 2^N \end{aligned}\end{split}\]

Therefore, \(TC(x)\) is the additive inverse of \(x\) for \(\bmod\ 2^N\).

Overflow

When adding numbers in a circuit, we are limited to the number of bits in our registers. (32 and 64 bit systems are common). This means that any carry over past the Nth bit is discarded. As shown previously, discarding this bit often does no harm (\(-7_{10} + 7_{10}\) in a 4-bit system). However, there are cases where the sum of two numbers is greater than the limits of the system and this can cause problems.

For example in the 2’s complement system, consider \(7_{10} + 7_{10}\) for a 4-bit system:

  0111    (+7)
+ 0111    (+7)
------
  1110    (−2)   ✗ Bad news ≠ 14

→ The leading one signifies a negative number, but two positive numbers should never sum to a negative for regular addition. This is known as overflow error. It happens when the sum goes past the upper limit of \(2^{N-1} - 1\) for positive numbers, or \(-2^{N-1}\) for negative numbers.

Most systems will check for overflow by seeing if the sum of two positives returns a negative or vice versa.

Binary Multiplication

Binary multiplication works exactly the same as multiplication you are used to, except is much easier because you are only multiplying by 0 or 1.

     1001
   × 1011
   ------
     1001
    1001
   0000
+ 1001
---------
  1100011

Note that whenever there is a multiplication by 1, this results in a shift of one of the multiplicands.

Multiplier circuits are thus shift registers that perform repeated shift and add operations.

Division is similar, except it is shift and subtract. Division ends up being much slower because all the additions in multiplication can be parallelized, but subtraction to find the remainder cannot. It ends up being an iterative process where there has to be constant checks to see if the subtraction led to a negative number (and therefore the number did not fit).