Operating System Design :: Lessons :: Boolean Arithmetic
Binary Numbers
This lesson is a synopsis of Chapter 2 from the book Building a Modern Computer From First Principles. After reading this synopsis you should read that chapter.
Normally, we represent numbers in decimal notation, also known as base 10. Decimal notation uses 10 digits (0-9) to represent numbers. We use this notation because it matches the number of fingers we have on our hands. Binary notation, or base 2, uses 2 digits (0-1) and is used by computers because of the on/off nature of an electric current. Below are the first 32 numbers (0-31) displayed as decimal and binary. You may sometimes find it easier to display leading 0s when using binary so the numbers below are displayed with leading 0s. Those leading 0s are not necessary so feel free to leave them off if you can understand the numbers without them.
| Decimal | Binary |
|---|---|
| 0 | 00000 |
| 1 | 00001 |
| 2 | 00010 |
| 3 | 00011 |
| 4 | 00100 |
| 5 | 00101 |
| 6 | 00110 |
| 7 | 00111 |
| 8 | 01000 |
| 9 | 01001 |
| 10 | 01010 |
| 11 | 01011 |
| 12 | 01100 |
| 13 | 01101 |
| 14 | 01110 |
| 15 | 01111 |
| 16 | 10000 |
| 17 | 10001 |
| 18 | 10010 |
| 19 | 10011 |
| 20 | 10100 |
| 21 | 10101 |
| 22 | 10110 |
| 23 | 10111 |
| 24 | 11000 |
| 25 | 11001 |
| 26 | 11010 |
| 27 | 11011 |
| 28 | 11100 |
| 29 | 11101 |
| 30 | 11110 |
| 31 | 11111 |
Signed Binary Numbers
So far when we have discussed binary numbers we have only dealt with positive numbers, but it is important to have a way to represent negative binary numbers as well. Humans use a signed-magnitude system when dealing with decimal numbers by adding a + or - in front of a number to indicate whether it is positive or negative.
The most common method used for storing signed numbers on computers is the two's complement system. Two's complement numbers store the sign as the first bit so a number with a 1 in front is negative while a leading 0 indicates a positive number. You can always find the opposite of a two's complement number by finding its complement, or opposite value, and adding 1. You should also drop the first bit if it extends past the number of bits used in the system. So if you ended up with a 9-bit number in an 8-bit system you would drop the first digit. Below are some examples of binary numbers in two's complement form:
| Decimal | Two's Complement Binary |
|---|---|
| 127 | 01111111 |
| 126 | 01111110 |
| 2 | 00000010 |
| 1 | 00000001 |
| 0 | 00000000 |
| -1 | 11111111 |
| -2 | 11111110 |
| -127 | 10000001 |
| -128 | 10000000 |
To understand how two's complement works look below to see how we converted from the positive numbers to the negative numbers. The ' sign means we are taking the complement of a number.
011111111' = 100000000 100000000 + 1 = 100000001(-127)
00000010' = 11111101 11111101 + 1 = 11111110 (-2)
00000001' = 11111110 11111110 + 1 = 11111111 (-1)
Now look what happens when we try to convert 0 and -128 assuming we are using an 8-bit system.
00000000' = 11111111
11111111 + 1 = 100000000 = 00000000
10000000' = 01111111
01111111 + 1 = 10000000
The reason the two above cases gave us strange results has to do with how two's complement form works. In two's complement there are more negative numbers than positive numbers so you cannot find the complement of the smallest negative number. This means the range of numbers in an n-bit two's complement system is
-2n-1 to 2n-1- 1
. One of the benefits of two's complement is that it only has one way to represent 0. Some signed number system have both a positive 0 and a negative 0. When you try to find the complement of 0 it results in an overflow so the final result gives you 0 again.
The main benefit of a two's complement system is how easy it makes addition, subtraction, and other mathematical operations. This is the reason why it is used for most computer systems.
Adding Binary Numbers
Addition in two's complement form is fairly simple. You simply add all the bits together as you would in decimal form and ignore any carry out. Below are some examples. Any red digits are carry out that is ignored when converting the final answer.
11
0111 (7)
+1100 (-4)
10011 (3)
11
1101 (-3)
+1110 (-2)
11011 (-5)
111
0111 (7)
+0001 (1)
1000 (-8)
The final calculation above is incorrect because adding 1 to 7 in a 4-bit system would result in an overflow so the sign-bit is changed incorrectly. This is why you will see integer values suddenly become negative when you go past the integer maximum in Java instead of crashing your program.
Adders
Addition is an integral part of any computer architecture. Therefore, there are a number of chips used to implement addition. A half-adder is designed to add two bits. The two outputs of a half-adder are the sum and carry.
A full-adder also outputs a sum and a carry, but it is designed to add three bits at a time.
Finally, an adder adds up n-bits depending on the computer platform. Typically this is 32 or 64 bits in today's computers. The image below is a 16-bit adder, but the architecture is similar for larger adders.
The Arithmetic Logic Unit
The arithmetic logic unit, or ALU, is the crucial chip for any computer architecture that executes all arithmetic and logical operations of the computer. The ALU below takes two 16-bit inputs and outputs a 16-bit value. There are also six control bits used to tell the ALU what function to execute. This results in 26, or 64 different functions the ALU can run. 18 of those functions are listed in the truth table below.The zr output is true if the output is 0 while the ng output is true if the output is negative.
