Binary

1s and 0s

Digital electronics makes a major simplification to the world of electronics through one simple rule: a signal means one of only two things. If there is voltage, the signal is called "1," and if there is not voltage, the signal is called "0." The only two states we care about are on and off, or 1 and 0. We don't have any fixed rules for what that state represents, or what we are to do with it. But we neatly sidestep a lot of the problems of component precision and cumulative mathematical error by reducing a signal level to a logical state.

Of course, this seems incredibly limiting. If I want to express the number "42," or the word "kumquat," or a picture, I need a lot more than two choices! But in all these cases the information is encoded as some collection of 1s and 0s. More complex information simply takes more of these states. The particular encoding of text or pictures can take a lot of different forms, but microprocessor systems use a consistent representation for integer numbers, and that representation is binary.

Number bases

We don't usually think about it, but our system of representing numbers is based on the fairly arbitrary decision that there are exactly ten symbols to represent numbers. These symbols, or "digits," are the characters 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. For any count from 0 to 9, we have a symbol to represent it. For any count higher than 9, we start to use more than one symbol. The number "10" doesn't introduce a new symbol; it simply uses the symbols "1" and "0." However, when we place them together, the first symbol represents the number of tens and the second symbol represents the number of ones. We are essentially representing the value "ten" as a simple equation of "one times ten plus zero times one." It is only that we have become accustomed to reading the meaning in a number with multiple digits that we don't think about this math.

Our system of numbering is called "decimal," or base ten. Any number base has a set of symbols, from zero through one less than the base, and each place value as you move from right to left is the next power of the base. The rightmost digit in decimal is ones (10⁰), then tens (10¹), hundreds (10²), thousands (10³) and so on. Digital logic uses binary, or base two. The rightmost digit is ones (2⁰), then twos (2¹), fours (2²), eights (2³) and so on. Obviously, the same number generally takes more digits to represent in binary than it does in decimal.

To express the number "42" (decimal) in binary, we look for the powers of two we need to combine to reach that value. The powers we need (in decimal) are 32, 8 and 2. Thus the binary value would be "101010." Similarly, to convert the binary value "11001100" to decimal, we would add the powers represented:
    128 + 64 + 8 + 4 = 204 (decimal)

Binary math

In our first years of school we had to memorize our math tables, for addition, subtraction and multiplication. We studied and drilled on all the combinations of 0-9. We didn't have to memorize, for example, 13+27, because we knew the rules for individual digits: three plus seven equals zero carry one; one plus two plus carry one equals four; the answer is forty. Binary similarly reduces to small tables. But since there are only two digit symbols rather then ten, the tables are very simple!

The entire "addition table" in binary is:
    0+0=0   0+1=1   1+0=1   1+1=10
Only the last one is any different than you knew from decimal, and that's only because we can't represent "2" with a single symbol.

The multiplication table is equally simple:
    0x0=0   0x1=0   1x0=0   1x1=1
No surprises here either.

The sum of 1 plus 1 overflows into another digit. Just like in decimal, this causes a carry. If we were adding 11 and 101, the result would be 1000 because each of the three digits caused a carry into the next digit. Multiplication follows the same rules you already know of multiplying each digit in turn and adding the individual values, shifted by the appropriate number of digits. So if we multiply 11 and 101, you would get 11+0+1100, or 1111.

Fixed digits

We are accustomed to writing numbers using the number of digits needed and no more. However we can accept that adding zeroes to the front of a number has no effect on the value: when a car odometer shows "001,234" we can agree that this is identical to the number 1,234. This is relevant to our discussion of binary because we are concerned with digital electronics and microprocessor systems, where every digit requires some supporting hardware. So we generally are not just talking about a binary number, but a binary number with a particular number of digits.

In computers we very frequently deal with "bytes," which are groups of exactly eight binary digits. When we write a binary value represented by a byte, then, we always write eight digits no matter how big the value actually is. So our example of 42 (decimal) would be written...
    00101010
...while a number like 1,234 (decimal) doesn't fit and cannot be represented in a single byte. Just like an odometer, there is a point of overflow when the number you see is smaller than the number intended.

A byte can represent any number from 0 to 255 (decimal).

Negative values

So far I have only talked about representing positive integer numbers in binary. But what if you want to represent a negative number? It would be reasonable to express -42 (decimal) as -101010 (binary), and to represent that in electronics with an extra digital state to indicate the sign of the number. However when dealing with a fixed number of binary digits, the more common representation is called "two's complement."

I already likened a fixed number of digits to a car odometer. What would happen if you could step the odometer backwards? You might count down to 000,002, then 000,001, then 000,000... and you know what would come next: the counter would wrap around ("underflow") to 999,999. The same thing happens in binary with a fixed number of digits: if you counted down in byte values you would see 00000010, 00000001, 00000000... and then wrap around to 11111111.

So for instances where we want to represent a signed value, we make a rule that says that any set of digits where the highest digit is "1" actually represents a negative number. By this rule, a signed byte can only represent positive values from 0 (00000000) through 127 (01111111). When the sign "digit" is set, the value is an underflow; take the positive integer represented if the value were not signed, and subtract the next power of 2 beyond the number of digits. That is, to interpret the signed eight-digit value "11111111," you first treat it as a positive integer (255 decimal), then subtract the next power of 2 (256) to yield -1. This makes sense; we got 11111111 by taking one away from zero, and you would hope that would mean -1!

There is another way to convert to and from signed values. A binary "complement" is when, for a given number, you swap all the zeroes for ones and all the ones for zeroes. "Two's complement" is when you complement all the digits and then add one. So, going from 1 to -1, you start with the binary value (00000001), then complement it (11111110), then add one (11111111). Going the other way, you start with the binary value (11111111), then complement it (00000000), then add one (00000001).

When we start using one place in a byte to represent a sign rather than a numeric symbol, it starts to seem silly to call all the places "digits." Actually, the more common term is "bit," short for "binary digit." We say that eight bits make a "byte," and the bits can represent digits or other logical states as needed. The leftmost ("high") bit has a different meaning for signed bytes than for unsigned bytes.

A signed byte can represent any number from -128 to 127.

Hexadecimal

One problem with binary as a number representation is that it is so long! It takes lots of digits to express anything. When writing or entering these numbers it is easy to make mistakes. So a more convenient representation often used in digital electronics and computers is hexadecimal, or base 16.

In hexadecimal we simply take every group of four bits (half a byte, called a "nibble;" cute, huh?) and assign a symbol to the sixteen possible values from 0 through 15 (decimal). What symbols? 0 through 9 are simply 0 through 9, while 10 through 15 are the letters A through F. Thus the number 13 (decimal) is D in hexadecimal.

If the math tables for binary are much easier than decimal, the math tables for hexadecimal are much harder than decimal, because you would have to learn all combinations from 0 through F (256 combinations each for addition and multiplication, rather than the 100 combinations in decimal). Here's a simple suggestion: don't bother. You use hexadecimal simply as a shorthand way of talking about binary numbers, not for doing arithmetic. When talking about lots of bits, it's just easier to say "12345678" in hexadecimal than it is to say "00010010001101000101011001111000."

Next: Logic Gates

Previous: Electricity

Copyright ©2003-2006, Mark Bereit. All rights reserved.