Number Systems & Binary

10 Sep 2018 in CS 101

Covering number systems, binary numbers, and binary representations

1. Positional Numbering & Bases
2. Binary Numbers
3. Binary Arithmetic
4. Fixed-Size Representation
5. Two’s Complement
6. Octal & Hexadecimal

Positional Numbering & Bases

The positional numeral system is a system of numbers by an ordered set of numeral symbols (aka digits) for which the value of a numeral symbol depends on its position. In other words, the value of the digits is known by their place.

For example, the number system that we know and use is base 10 (decimal notation). Base 10 uses 10 numeral symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. So, to read a number in base 10, we rely on each digit’s place value. To illustrate: 639 can be read as six hundred thirty nine and written as 6 x 100 + 3 x 10 + 9 x 1.

Base 10 is not the only base there is. In fact, we can use any number we can think of as a base in the positional numbering system. For instance, let’s try out base three. In base 3, the numeral symbols we can work with are 0, 1, and 2. This is like in base 10, where the symbols we use are 0 to 9.

The number above, 201 in base 3, is equal to 19 in base 10. Why? Because 201 (in base 3) is 2 x 9 + 0 x 3 + 1 x 1 which equals 19 (base 10).

Now, what do we do when we want to convert from base 10 to a foreign base?

One method (perhaps the quickest) is to create a bunch of slots and label them according to the base we want to convert to. In the problem above, we want to convert 65 to base 3. I stopped created slots when I reached the eighty ones position because I realized that 81 is too large for any integer to multiply by it and “fit” into 65. So, we’ll put a 0 in the eighty ones position and move to the next slot: the twenty sevens position. Here, 2 x 27 ( = 54) is the largest multiple of 27 that can fit into 65. Let’s put a 2 in that slot. Our remainder (what we have left of 65 to work with) is 65 - 54 = 11.

Next is the nines position. How many nines can fit into our remainder, 11? 9 x 2? No, that’s too big. 9 x 1? Yes! Let’s put a 1 in the nines position and calculate our remainder (11 - 9 = 2).

Let’s continue to the threes position. How many threes can fit into 2? None. We put a 0 in the threes position and calculate our remainder (3 - 0 = 3). Let’s try the ones position. 2 x 1 is 2, so we put a 2 in the ones position and calculate our remainder.

That’s it! Our answer: 65 converted into base 3 is 2102.

Additional Resources: Khan Academy - Intro to Number Systems & Binary

Binary Numbers

Computer systems speak in binary (base 2) numbers. Using two as the base is the lowest level of abstraction. In other words, binary is as basic as number systems get. We only need two numeral symbols, 0 and 1, and we can still represent many things: a light switch turned on or off, a signal sent or not sent, a value true or false, a quantity positive or negative, and so on.

A zero is a slot means that exclude that position’s value, and one means that we include it. SO the binary number 01101 is the quantity 8 + 4 + 1 = 13. Each binary digit in 01101 is called a bit. Therefore, in this number there are five bits. The largest five-bit binary number is 11111 which is 16 + 8 + 4 + 2 + 1 or 31.

Let’s try converting the number 37 to binary. We could use the same method of creating slots and, starting from the largest slot, we’ll work our way down to see what “fits”.

There is also another method. It has to do with a special property of numbers raised to the second power: they’re all even! So let’s convert 37. We begin by noticing that it is odd, so we put a 1 and divide by 2. 37 / 2 = 18.5 and discard the remainder ( = 18). 18 is even, so we write a 0. 18 / 2 is 9 which is odd, so we write a 1, and so on.

In reading the numbers from bottom to top, we get 37 in binary is 100101.

Additional Resources: Techquickie’s Video on Binary Numbers

Binary Arithmetic

Adding two binary numbers is practically the same as adding two base 10 numbers: line up the columns and then proceed from right to left.

However, in binary there are only four possible cases:

• If a column has no ones, write a zero below. 0 + 0 = 0
• If a column has one one, write a one below: 1 + 0 = 1
• If a column has two ones, write a zero and carry a one to the next column: 1 + 1 = 1 with carry of 1 to the left column.
• If a column has three ones (due to an incoming carry), write a one and carry a one to the next column.

Below is an example of adding 10110 and 11100. The result is 110010, and you can see the four possible cases below.

We can also check our answer by converting both 10110 (= 22) and 11100 (= 28) as well as our answer 110010 (= 50) to decimal notation. We find that 22 + 28 = 50, so our answer of 110010 is correct.

Fixed-Size Representation

In base 10 notation, we can arrange numbers along a number line and, in either direction, it goes off into infinity. In binary, we can do the same. We can keep counting and adding more slots that are powers of two.

However, in many computer systems, we use fixed-size numbers. This means that the number of bits we can use is already determined. For example, a 4-bit computer represents most of its numbers and addresses using exactly 4 bits. The largest such number is 2<sup>4</sup> - 1 or 1111 which is equal to 15. In a 32-bit computer, the largest number is 2<sup>32</sup> - 1 = 4,294,967,295. Today, many computers now use 64-bits for which the largest number is 2<sup>64</sup> -1 = 18,446,744,073,709,551,615.

When your numbers have a fixed size, there is no number line heading off to infinity. Instead, the numbers are arranged around a circle or wheel. Below is the number wheel for 3-bit binary.

Above is the number circle for 3-bit integers. The smallest is zero and the largest is seven. If you attempt to keep counting beyond 7, it simply wraps around to zero again.

Why? When you perform arithmetic with fixed-size numbers, you throw away any extra carry bit because you cannot exceed the given size. For example, see what happens when we try to add 110 + 010 using 3-bit numbers.

In 3-bit arithmetic, 6 + 2 is 0. This makes sense if you think of it like walking clockwise around the number wheel. Start at 6 and move clockwise 2 spaces. We land on 0, which is 6 + 2.

Additional Resources:

• Computerphile’s Review on Binary Addition & Overflow
• Numberphile’s Explanation of 255 and Pac-Man

Two’s Complement

Up until now, it seems that binary can do almost everything that base 10 can. But how can we represent negative numbers in binary? One way to do represent signed numbers (positive or negative numbers) is called two’s complement. Below is the general layout of a 4-bit two’s complement. All we need to do in two’s complement is to make the value of the left-most bit negative.

To represent 6 in binary, we write 0110 because 4 + 2 equals 6. But to write -6 in binary, we write 1010 because -8 + 2 = -6.

Likewise, to write -1 in binary, we write 1111 because -8 + 4 + 2 + 1 is equal to -1 in two’s complement.

It is important to note that the rules for binary addition also apply (and work!) for two’s complement:

It is also easy to negate a number, that is, to go from +4 to -4 or from -8 to +8. The steps for going from:

1. Invert all the bits. In other works, all the ones become zeros and all the zeros become ones.
2. Add one.

For example, to calculate -6, we know that 6 is 0110 and all we have to do is negate it.

1. Invert the bits: 0110 becomes 1001.
2. Add one: 1001 + 1 = 1010 (which equals -6)

To go from -6 to +6, we don’t have to reverse these steps. Just do the same.

1. Invert the bits: 1010 (-6) becomes 0101
2. Add one: 0101 + 1 = 0110 (which equals +6)

Octal & Hexadecimal

The octal (base 8) and hexadecimal (base 16) systems are useful as abbreviations for binary. Octal and hexadecimal work well because 8 and 16 are powers of two.

Octal uses the symbols 0 through 7 and the value of its columns are:

The advantage of octal is that each octal digit maps to three binary digits.

Hexadecimal is base sixteen, so we use the symbols 0 through 9, and A to represent 10, B for 11, C for 12, and so on up to F for 15. The values of the slots are:

So, the hexadecimal number 2A5C has the value 2 x 4096 + 10 x 256 + 5 x 16 + 12 x 1 which is equal to 10844 in base 10.

In hexadecimal, each digit maps to exactly four bits in binary.

Additional Resources:

• Numberphile’s Video on Hexadecimal
• Schafer on Hexadecimal & Octal