Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Build a Computer - September 25, 2018 :: Network App - December 14, 2018

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.

Half-Adder

A full-adder also outputs a sum and a carry, but it is designed to add three bits at a time.

Full-Adder

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.

16-Bit Adder Arithmetic Logic Unit

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.

Arithmetic Logic Unit Truth Table
Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram