Number Systems
Numbers are useful. It's likely that numbers and their many uses are some of the first concepts you were taught as a child, and no doubt you have been using them regularly throughout your life. So it is no surprise that we would also like to represent numbers in digital systems.
Before moving on, it is critically important that you realize that numbers are a concept. They abstract physical reality, but they are not real. This is important because it is easy to believe that the number system you have learned about your whole life (decimal) is "correct" and that other number systems are somehow fundamentally different. It's true that different number systems have certain benefits, but the fact is that they are all just abstractions of reality -- they are a tool that we can use to help us design useful things.
Representing Numbers in Digital Systems
Since everything in a digital system must be discretized to two values (on/off, up/down, or the generic true/false and 1/0), at first glance it might seem like we could only ever represent two numbers. Maybe a signal being low could represent 7, and it being high could represent 95. But clearly that is not going to be very useful.
To overcome the limitation of only having two values, we can consider multiple signals together, and use the different combinations of those signals to represent different things (in this case, different numbers). For example, if there are three signals, and each one represents whether or not a particular cow is in a barn, then we (as a human) can consider the combinations of signals to represent "how many cows are in the barn."
| Cow1 | Cow2 | Cow3 | Decimal Representation of Number |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 2 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 2 |
| 1 | 1 | 0 | 2 |
| 1 | 1 | 1 | 3 |
However, this method of representing numbers is inefficient, because it creates multiple ways to represent the concepts of '1' and '2', in a sense wasting those combinations of signals.
Instead, the most common way to represent numbers in a digital system uses the same concept as the decimal system you are familiar with: use the position of digits to represent different powers of the base number. It has probably been at least a decade or so since this was specifically pointed out to you, but in a number like 365, the '3' doesn't just represent '3' -- being in that specific location means that it instead represents 3×102. And the 6 represents 6×101, and the 5 represents 5×100.
This type of number system is called a positional system or a based system. The choice of 10 as the base is arbitrary. (No one knows for sure why we use 10, other cultures have used 12, 20, and even 60 as the base, and 10 is actually inconvenient in a lot of ways but we're stuck with it because we all use it now.) Positional number systems are not the only way to represent numbers (consider Roman numerals like Ⅶ, or a simple tally system), but they have some very useful properties when it comes to arithmetic, which is why they are almost universally used today.
To use a positional number system, you need the same number of symbols as your base. Base-10 (decimal) has ten symbols: 0, 1, 2, up to 9. In a digital system, each signal can only represent two symbols (high/low, true/false, 1/0), so the choice of base is clear: it will use a base-2 system.
When discussing numbers in different bases, a common way to express the base is with a postfix subscript, e.g. 36510 or 112.
Binary
A base-2 positional number system is called binary. To keep things concise, and to be consistent with the numbers we typically use, the two symbols used in binary are 0 and 1.
The phrase "binary digit" is often shortened to "bit," so we can talk about the number of bits in a number (you have probably seen your computer's processor described as 64-bit, which means that it operates on numbers with 64 binary digits), and we can say things like "the least-significant bit" (the right-most place value).
Each successive position in a binary number represents an increasing power of 2. Since we are so used to base-10, viewing these numbers as their base-10 equivalent can be beneficial to help get a feel for how binary numbers work.
| position | base-10 representation | base-10 value |
|---|---|---|
....1 |
20 | 1 |
...1. |
21 | 2 |
..1.. |
22 | 4 |
.1... |
23 | 8 |
1.... |
24 | 16 |
(As a side note, even calling this "base-2" is using the number system we're familiar with. Literally every positional number system would be called "base-10" if described using its own base.)
Just like in decimal, a number's total value is the sum of each of the digits multiplied by that digit's positional value. Since in binary each digit can only be 0 or 1, either there is or there isn't a contribution from that place value. That means that to convert a binary number to decimal, you can simply sum the decimal equivalent of the place values with 1s. For example,
Converting a number in decimal to its representation in binary requires determining what power-of-2 components are needed. A simple algorithm to achieve this is to repeatedly take out the largest possible power of 2. For example, starting with 156:
| Remaining amount | largest power of 2 |
|---|---|
| 156 | 27 (128) |
| 28 | 24 (16) |
| 12 | 23 (8) |
| 4 | 22 (4) |
| 0 | - |
So the binary representation is 10011100 (1s in the 7th, 4th, 3rd and 2nd places, assuming that the least-significant digit is called the 0th place)
We already know that N signals can, together, be in 2N different combinations of 1s and 0s. Since, in binary, each combination represents a unique integer, and those integers start at 0, an N-bit binary number can represent the range of integers from 0 to 2N-1 (base-10). Going the other way, representing a particular base-10 value M requires ⌈log2(M+1)⌉ bits.
Hexadecimal
Since each binary digit has so many fewer possibilities than a decimal number, binary numbers must have more digits than a decimal number to represent the same value. Even to represent values in the thousands, ten or more binary digits are needed, which makes them difficult to read and cumbersome to write. To alleviate this downside while still representing numbers in a form convenient for digital systems, we can use larger bases that are still powers of 2.
Consider a group of four binary digits. There are 16 different combinations of those digits, which means that if we use a base-16 number system, each symbol can correspond directly with a combination of four binary digits. This number system is called hexadecimal. Since it requires 16 symbols, those symbols are typically the numerals 0-9 and then the letters A-F.
| binary | hexadecimal | decimal |
|---|---|---|
| 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 | 9 |
| 1010 | A | 10 |
| 1011 | B | 11 |
| 1100 | C | 12 |
| 1101 | D | 13 |
| 1110 | E | 14 |
| 1111 | F | 15 |
As a positional number system, all of the rules and capabilities of positional numbers apply to hexadecimal. But since each hexadecimal digit directly corresponds to a combination of four binary digits, converting between the two is trivial.
Signed Magnitude
Representing negative numbers in a digital system is not as simple as adding a "-" in front of it, because everything must be represented as Boolean information. Of course, a Boolean signal could be used to simply represent whether or not a number is negative. This is called a signed magnitude representation (sometimes called sign-magnitude) because that's literally what it is: one bit to represent the sign (positive or negative) and one or more bits to represent a magnitude (using the positional system described above).
The most common standard uses the left-most bit to represent the sign (noting that it can't be called the "most-significant" digit here because it does not represent magnitude), and uses the convention that a '1' represents the number being negative. So, for example, the 7-bit signed magnitude number 1000001 represents -110.
While signed magnitude representations are simple and have their uses, they have some drawbacks. Mainly:
- It's possible to represent "-0," which wastes a combination of signals, and could require extra consideration depending on what you are using the numbers for.
- Mathematical operations (addition, etc.) are more complicated than with a purely positional number system, because the sign needs to be accounted for separately from the magnitude.
Two's Complement
Although, conceptually, binary numbers are boundless (like all numbers), in a digital system, physical hardware is required to carry the digital signals representing the number, which means that the number of bits is always fixed -- once you make the hardware, you can't just write another digit to increase the size of the number.
If a number has a fixed size, an interesting thing happens when you increment it beyond its limit. Consider a two-digit decimal number. When counting up, you would reach 98, then 99, but then if you increment it again, you would get 00, because there is nowhere to put the extra digit that would be needed to represent 100. So a fixed-length number inherently enables modular arithmetic. And modular numbers enable an elegant way to represent negative values.
When you were learning to count and do simple math, you likely used a number line. But since continuing to increment a modular number eventually brings you back to 0, the numbers can be represented on a number circle. Consider a 4-digit binary number. Its number circle would look like this:
Just like with a number line, addition can be shown by starting at one number and incrementing as many times as needed for the second number. Something like "3+4" (using decimal numbers to keep things easy to think about) would look like this, which shows that indeed the result is 7 (or the binary representation of 7).
However, use the above number circle to do something like 6+15 and see what happens -- the answer is 5. It's as if "15" behaves like "-1," since adding it to 6 had the overall effect of decrementing by 1.
We can use this to our advantage by using the binary sequence 1111 to represent the concept of -1. Similarly, it makes sense to use 1110 to represent -2, and so on, down to 1000, which would represent -8.
This is a good time to remind you how important it is to not try to shoehorn what you are learning here into the number system you are experienced with. Numbers are concepts, and the idea of a number can be represented in many different ways, like how "4" can be represented as Ⅳ, or as ||||, or as 四.
This interpretation of bits is called two's complement binary. Its main benefits are that it works nicely with arithmetic (covered later) and that it doesn't have a -0 (though it does have the edge case that its most-negative value does not have a positive representation).
| 4-bit 2's comp binary | decimal representation |
|---|---|
| 0000 | 0 |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 3 |
| 0100 | 4 |
| 0101 | 5 |
| 0110 | 6 |
| 0111 | 7 |
| 1000 | -8 |
| 1001 | -7 |
| 1010 | -6 |
| 1011 | -5 |
| 1100 | -4 |
| 1101 | -3 |
| 1110 | -2 |
| 1111 | -1 |
You probably noticed that for the first half, two's complement numbers are the same as unsigned binary numbers. This pattern extends to numbers with more bits: if the leading digit is 0, the number can be interpreted in the same way as unsigned binary, and it represents a positive value. However, if the leading digit is 1, then the value is negative and must be interpreted differently.
Note that although the leading digit being 0 or 1 does indicate that the number is positive or negative, that bit does not mean the sign like it does in a signed magnitude number.
One way to find the magnitude of a negative two's complement number is to negate it, which will make it positive so that its magnitude can more easily be determined. Conveniently, two's complement has a simple algorithm for negating a number: flip each of the bits, and then increment by 1. For example,
0111 (decimal 7)
1000 (flip all the bits)
1001 (increment by 1; this now represents decimal -7)Of course negating twice should return to the original number, so
1001 (decimal -7)
0110 (flip all the bits)
0111 (increment by 1; this now represents decimal +7)This works for two's complement numbers with any number of bits, so for example if you needed the 8-bit two's complement representation of -57, you can negate 8-bit +57:
00111001 (+57)
11000110 (flip all the bits)
11000111 (increment by 1; this represents -57)Another way to convert two's complement numbers to decimal is to view the leftmost digit as the negative of that position's value in unsigned binary. For example, in a 5-bit two's complement number, the leftmost digit can be interpreted as -(24).
Fractional Representations
In decimal numbers, a fractional separator (a "decimal point") is used to mark the location of the 1's place (100), and just as places to the left increase the power of the base, moving right decreases it. The digit to the right of the point represents a multiple of 10-1, the next digit 10-2, and so on.
Exactly the same concept works with binary numbers. A number like 110.011, interpreted as an unsigned binary number, represents a whole part of 610 (110), and a fractional part of 2-2+2-3=0.37510, so in total it represents 6.37510.
If representing negative fractional numbers is needed, two's complement works directly with this system. The number above, 110.011, if interpreted as a 2's complement number, is equivalent to -1.62510. You can confirm by negating the number (using the same algorithm described above) and then finding its magnitude.
Note that in digital hardware, nothing is physically used to indicate the distinction between the whole and fractional parts. Numbers don't "mean" anything to hardware; everything is just voltage on wires. When designing a system, you as the engineer decide how many bits will be used for each part, and then those signals have meaning to you. This is called a fixed-point representation, because once you decide where the fractional separator is, it stays there (in your mind) and you design the system around that.
Contrast that with floating-point numbers. We won't go into detail on floating-point in this class, but the idea is that some bits can be used to encode the location of the fractional separator. This allows hardware to be designed that correctly performs arithmetic on numbers over a much wider range (but not with any extra resolution). You can read more here if you are interested.
Summary
- Combinations of Boolean signals can be used to represent numbers.
- If only positive integers are needed, an efficient and convenient way to represent numbers is to use a base-2 counting system.
- If positive and negative numbers are needed, options include signed magnitude and two's complement representations.
- If fractional numbers are needed, options include fixed point and floating point numbers.
- Always remember that just like a string of symbols like "422" represents the concept of a specific numerical value, strings of bits can also represent numerical values, but the specific interpretation of those bits varies in different number systems.