Binary arithmetic is easy, so easy a computer can do it, but what about negative numbers? This is altogether more tricky and isn't just a matter of putting a negative sign in front of the number - although that is one way to do it..

What Programmers Know

Contents

1. The Computer - What's The Big Idea?*
2. The Memory Principle - Computer Memory and Pigeonholes*
3. Principles of Execution - The CPU
4. Assemblers and assembly language*
5. The Essence Of Programming
6. Variables - Scope, Lifetime And More*
7. Binary Arithmetic
8. Hexadecimal*
9. Binary - Negative Numbers*
10. Floating Point Numbers*
11. Inside the Computer - Addressing
12. The Mod Function
13. Recursion
14. The Lost Art Of The Storage Mapping Function *
15. Hashing - The Greatest Idea In Programming
16. Advanced Hashing
17. XOR - The Magic Swap*
18. Programmer's Introduction to XML
19. From Data To Objects*
20. What Exactly Is A First Class Function - And Why You Should Care*
21. Stacks And Trees*
22. The LIFO Stack - A Gentle Guide*
23. Data Structures - Trees
24. Inside Random Numbers
25. The Monte Carlo Method
26. Cache Memory And The Caching Principle
27. Data Compression The Dictionary Way
28. Dates Are Difficult*
29. Sequential Storage*
30. Magic of Merging*
31. Power of Operators
32. The Heart Of A Compiler*
33. The Fundamentals of Pointers
34. Functional And Dysfunctional Programming*

* Recently revised

Being negative about binary

Binary is the computer way.

While we might carry on using our outmoded base ten methods with the most minor of excuses - why let the possession of ten fingers influence your choice of number base - computers do everything with zero and one. We have already looked the basics of why binary arithmetic is so attractive from a computer's point of view.

Put simply you can represent a binary number using nothing but two electronic states - usually high and low voltage. You can also manipulate a binary number using Boolean logic and, while the connection between logic and arithmetic is far from obvious, it does all fit together unreasonably well.

Notice that there is no such cosy relationship between decimal notation and any sort of easy to implement logic.

Logic and arithmetic

Two-valued arithmetic and two-valued logic fit so well together that you almost don't notice that they are quite different things. You can be talking about Boolean logic one minute with truth tables, And, Or and Not gates, and the next you are dealing with half and full adders that appear to be all about logic but designed to do arithmetic.

The point is that Boolean logic simply realizes the "addition tables" that characterize binary arithmetic. That is, to add two bits together all you need is a lookup table of results:

                A B R C
               0 0 0 0
               0 1 1 0
               1 0 1 0
               1 1 0 1

If you want to add bit A to bit B to produce a two-bit result R and C then all you have to do is look up the entry in the table and read off the answer.

All arithmetic is done this way, using a lookup table, no matter what base you are working in.

Don't believe me?

Well how do you add 3 to 6?

You use a lookup table that was loaded into your, hopefully non-volatile, memory back when you were being instructed in such things. Without the lookup table you haven't a clue how to add two digits unless you actually "do" the addition, with marbles say, and count the final result.

In other words the basic addition of the symbols in any base have to be memorized in the form of a lookup table.

Once you have the addition table for the digits in any base then you can do addition of any multi-digit numbers by following the place value algorithm - add the first two digits, write down the result and pass the carry onto the addition of the next two digits and so on.

The only complication is that after the first two digits you have to involve the carry from the previous addition but this isn't too difficult.

The connection between binary arithmetic and Boolean logic is that its lookup table for addition can be treated as if it was a truth table and implemented using logic gates. What is interesting is that the lookup table for binary has only four lines but decimal has 100! You need to know what every digit added to every other digit gives as a result.

     C R
  0 0 0 0 
  0 1 0 1
  0 2 0 2
  0 3 0 3
   ...
  9 7 1 6
  9 8 1 7
  9 9 1 8

We don't really store a 100-line table in our head's because we are "clever" enough to notice the regularities - 0 added to any digit doesn't make any difference, adding one is just easy, x+y is the same as y+x and so on.

Still you do need to maintain 40 or so table entries to do decimal arithmetic and this is presumably why it is so hard to learn at first.

If we switched to binary a four-line table would at least be easy to remember.

Switching to octal

A short detour - feel free to skip to the next section.

If you think that the idea of switching our adopted base to binary is crazy it is worth pointing out that the closely related base 8 has been seriously proposed more than once.

King Charles XII of Sweden, an accomplished mathematician, proposed in 1717 that the whole country switched to base 8, then known as octonary or octonal.

Not just changing the weights measures, currency etc. but changing the way numbers were written down and arithmetic performed. He felt that base 8 or base 64 would be much more convenient for practical calculations than the old fashioned decimal system. He died in battle before he could implement the change but it is interesting to think what might have happened.

One hundred years later a Swedish engineer tried to resuscitate the plans but using base 16. Even the French nearly missed using the metric system because octal arithmetic seemed so much more appropriate.

It is also interesting to note that the common practice of calling the base 8 system “octal” rather than octonary or octonal is quite a recent invention - from around 1960. It stems from the use of 8-pin vacuum tube/valve bases and holders, which were, trademarked “Octal”.