10.1. Positional Number Systems#
Over time, humans have developed many ways to represent quantities with written number systems. In order to do so efficiently, most cultures developed what’s known as a positional number system. Instead of having to remember a unique written character for every number, it’s easier to have a short list of characters that can take on different values depending on their position in the number.
For example, base-10 representations of numbers (also known as decimal) use the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, which take on different quantities depending on if they are written at the beginning or the end of the number, and how many characters are needed to write the number.
When written furthest to the right, the numeral 5 represents the quantity five, but when written in second position (one from the furthest right) it represents the quantity fifty. This change in value depending on the position a numeral is written is the defining characteristic of a positional number system.
The base of a number system identifies the value of each position in the system and how many characters are needed. For example, in a base-10 system, each position is a power of 10, and only 10 unique characters are needed to represent each position in the number (0-9). Going from right to left, each position is valued at \(10^0 = 1\), \(10^1 = 10\), \(10^2 = 100\), \(10^3 = 1,000\), etc. The numeral written in each position indicates the multiplier for that value.
Therefore, the decimal number \(4,237\) represents:
Likewise, a base-2 number system would indicate that each position represents a power of \(2\) and needs only 2 unique characters to represent each position in the number. Again moving from right to left the positions are valued at \(2^0 = 1\), \(2^1 = 2\), \(2^2 = 4\), \(2^3 = 8\), \(2^4 = 16\), etc, and each position will use the characters \(0\) or \(1\).
For example, the number \(10011\) in binary represents:
Which can be expanded and simplified to be written as the decimal number \(19\). Both are representations for the same quantity, just written differently.
It’s important to note that numbers can be written using a variety of bases, not only \(2\) and \(10\). The other commonly used number system in computing is hexadecimal, which is base-16. In that system, the characters used are 0-9 for zero through nine and A-F for the values of eleven through fifteen. Many of these bases are chosen for a particular reason, for example:
Base-10 numbers are convenient because humans have 10 fingers
Base-2 numbers are convenient because computer transistors only have 2 states, on (1) and off (0)
Base-16 numbers are convenient because they can represent an 8-digit binary number using only 2 digits.
There are many other number systems that have been used throughout history. Their use varies between cultures, geographical regions, and practical considerations. A full list can be found at: https://en.wikipedia.org/wiki/Numeral_system.
Modern encryption uses data stored on computers and operations performed on computers to accomplish security, and since binary is the numerical system best understand by computer, we need to understand more about the base-2 number system and how to work with binary numbers.
Converting Decimal to Binary#
If you’re not used to working in base-2, then working with binary numbers may seem unnatural. However, binary numbers can be just as natural as decimal numbers with a bit of practice. This practice will ultimately pay off, as many algorithms that help gain efficiency in computation rely on binary expansions to achieve their astounding results.
Suppose you wanted to represent the decimal number \(42\) in base-2. As previously mentioned, numbers represented in base-2 use digits that represent powers of \(2\) (1, 2, 4, 8, etc.). To represent \(42\) as a binary number, you need to determine how to represent it as a sum of powers of 2, whose coefficients are either 0 or 1. Start by determining the largest power of \(2\) less than \(42\), which is \(32\). Subtracting \(32\) from \(42\) results in \(10\), and repeat. The largest power of \(2\) less than \(10\) is 8, subtracting gives \(2\), which by chance is already a power of \(2\).
To summarize, the decimal number \(42\) is the sum of the following powers of \(2\):
This can be more succinctly written as the base-2 number \(101010\). Sometimes you’ll see binary numbers written with a subscript of \(2\) after the number to emphasize that the number is written in base-2. It would not be uncommon to see \(42\) written as \(101010_2\).
However, if the base is understood, this subscript often goes unwritten. For example, you knew when reading \(42\) earlier it was written in base-10 based on context, and didn’t need it written as \(42_{10}\).
Binary Vocabulary#
When discussing binary, it’s important to remember the following vocabulary considerations:
When numbers are written in binary, we say that each position stores a single bit of information, either a 1 or a 0.
If a number requires \(5\) positions to represent in binary, we say that the number is a 5-bit number.
\(8\) bits of information are equivalent to \(1\) byte of information.
Counting in Binary#
Counting in both systems is a good way to get comfortable with base-2 numbers. When counting in base-10, you increase the digit in the 1’s place until you reach the largest digit, 9. Once you increase the number by 1 more, it’s easier to write the quantity as \(10\), signifying 1 unit in the 10’s place and 0 units in the 1’s place. When counting in base-2, you increase the digit in the 1’s place until you reach the largest digit, 1. Once you increase the digit by 1 more, it’s easier to write the quanitiy as \(10\), signifying 1 unit in the 2’s place, and 0 units in the 1’s place. Increasing by one more (3 in base-10) can be written as \(11\). Increasing by one more (4 in base-10) can be written as \(100\), representing 1 unit in the 4’s place, 0 units in the 2’s place, and 0 units in the 1’s place.
Counting is probably natural for you in base-10, but because base-2 only has two digits, 0 and 1, this can seem a bit awkward at first since you reach the largest digit in each place very quickly which causes a lot of new place values to be needed rather quickly.
Counting in base-10 and base-2 would result in the following table:
base-10 |
base-2 |
|---|---|
0 |
0 |
1 |
1 |
2 |
10 |
3 |
11 |
4 |
100 |
5 |
101 |
6 |
110 |
7 |
111 |
8 |
1000 |
9 |
1001 |
10 |
1010 |
It’s important to remember that each row represents two different ways to represent the same number. The last row containing \(10\) and \(1010\) both represent the quantity, “ten”. It would even be correct to read both as “ten” out loud, although it’s common to read the binary representation as “one, zero, one, zero”.