4 min read

On Binary Arithmetic

Binary arithmetic is not something that you’ll see very often in your everyday REST app, but that doesn’t mean that it’s not important to know (or at least to know about).

Arithmetic on binary numbers is really no different than it is on other number systems (i.e., bases), such as decimal. Let’s look at some examples.

Addition

Recall that when adding decimal numbers, any sum greater than 9 will carry over to the next number place. For instance, when adding the numbers 9 and 5, 14 is greater than 9, so the first number 1 will carry over to the ten’s place:

 1
  9
  5
---
 14

Every school kid knows this. And with binary, it’s the same, the only difference being that 1 is carried over to the next “column” when the sum is greater than 1:

1
 1
 1
--
102 == 210
 1
101
001
---
1102 == 410

Ok, that’s really straightforward. Let’s look at an example of adding larger numbers.

 1111 1111
0110 1111  <--- 11110
0101 1101  <--- 9310
---------
1100 11002 == 20410

Let’s break that down:

  • 1’s place: 1 + 1 = 2, write down 0 and carry a bit
  • 2’s place: 1 + 1 = 2, write down 0 and carry a bit
  • 4’s place: 1 + 1 + 1 = 3, write down 1 and carry a bit
  • 8’s place: 1 + 1 + 1 = 3, write down 1 and carry a bit
  • 16’s place: 1 + 1 = 2, write down 0 and carry a bit
  • 32’s place: 1 + 1 = 2, write down 0 and carry a bit
  • 64’s place: 1 + 1 + 1 = 3, write down 1 and carry a bit
  • 128’s place: 1 + 0 = 2, write down 1 and we’re done

If never having done this, it will probably feel a bit awkward at first, but once your brain gets used to thinking in number systems other than decimal it will become easier.

Subtraction

Subtraction is fun, at least until daddy takes the T-Bird away, and then it’s sort of a drag.

Most sites that I’ve looked at use a method of subtracting where bits are borrowed when needed from larger numbers, but I prefer converting the smaller number to twos’ complement form and then adding. This has the extra benefit of reinforcing and understanding twos’ complement.

Recall that twos’ complement is simply inverting all of the bits (i.e., ones’ complement) and then adding 1.

Let’s look at a simple example:

1001  <--- 910
0111  <--- 710

Twos' complement of 7: 1001

Add!

  1
1001
1001
----
00102 == 210

Recall that any overflow bit is discarded!

Let’s look at an example of subtracting larger numbers:

0110 1111  <--- 11110
0101 1101  <--- 9310

Twos' complement of 93: 1010 0011

Add!

111 1 1111
0110 1111
1010 0011
---------
0001 00102 == 1810

( Again, the overflow bit is discarded. )

Weeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

Multiplication

Binary multiplication is even easier than decimal multiplication. That’s kind of nice.

Bitwise AND is multiplication. Let’s look at the truth table:

* 0 1
0 0 0
1 0 1

So:

  • 0 * 0 = 0
  • 0 * 1 = 0
  • 1 * 0 = 0
  • 1 * 1 = 1

See, it’s just multiplication, I would never lie to you. And the bit is only 1 or true 25% of the time.

In addition, as in decimal multiplication, there are two parts to binary multiplication:

  1. Multiplying each bit, starting from the rightmost bit.
  2. Adding the results of the multiplications.

Keep this in mind for the following example:

   1101
    101
   ----
   1101
  0000
 1101
-------
1000001 --> 0100 00012 == 6510

The part that is easier than decimal multiplication is that for every 1 in the multiplicand (the second number in the equation), you can merely copy the entire number. Or, you can think of each bit and compute using the truth table above. Whatever floats your boat.

Division

I don’t really feel like covering division cause it bores me. Maybe I’ll come back to this article at some point and fill this part in. Oh well.