Unit 06 PDF

Preview

Summary

Unit 06 notes...

Description

Computer Science 132 Binary Numbers Bits, Bytes, binary number system and octal numbers

Measuring storage capacity of files in computers A bit is the smallest unit of information on a computer: it is either of a bit state of 1 or 0 (as on or off, true or false, etc). Building on bits, file storage is measured in bytes, the smallest unit of storage.

1 byte 1 Kilobyte (KB) 1 megabyte (MB) 1 gigabyte (GB) 1 terabyte (TB)

= 8 bits = 1024 bytes = 1024 Kilobytes = 1024 megabytes = 1024 Gigabytes

~ 106 bytes ~ 109 bytes ~ 1012 bytes

Why is eight bits required for a byte? A single character such as a letter or digit or punctuation mark currently requires a byte of storage on older computer systems. Someday, it might require two bytes on all systems, typical for advanced Unicode characters. Recall that a bit can only represent a single state of either being ‘on/true’ (1) or ‘off/false’ (0). A bit can only be one of two states. Computers need to be able to represent all characters on the keyboard, and account for Unicode.

Some binary math of bits to bytes… We use patterns of binary numbers to represent a typed character as bytes; How many patterns of bits will we need? Arithmetically, 2n patterns, so, how many patterns for n? To conform to the ASCII code (127 characters), and Unicode (accented characters; the other 128 characters), we need at least 255 patterns. Computers need, at least the minimum of 8-bits (2 states ^ 8 patterns = 256), to at least 256 possibilities to use for the 255 patterns.

The characters are therefore assigned using a zero-based system, to range from pattern 0 to 255. Binary numbers To make sense of how the bits and bytes are utilized by computers, you need to understand the binary number system. The decimal number system you know has ten digits: 0, 1, 2, 3, ..., to 9. The binary system has just two digits: 0 and 1. It is possible to represent decimal numbers in binary system. Starting from zero, are the first eight numbers in binary and decimal: Decimal Binary

0 0

1 1

2 10

3 11

4 100

5 101

6 110

7 111

You can figure out the sequence if you know how to add 1 to a binary number in the binary number system.

Binary numerals and exponential arithmetic In the decimal number system, there is the ones' place, the tens' place, the hundreds' place, going up by powers of ten, and so on. In the binary number system, there is the ones' place, the twos' place, the fours' place, the eights' place and so on, going up by powers of two. Read from right to left, the particular binary number 11001 has •

1 one’s place,

•

0 twos’ place,

•

0 fours’ place,

•

1 eights’ place, and

•

1 sixteens’ place,

for a total value of 1 + 8 + 16 = 25 in base ten. So, 11001 in binary, is 25 in decimal.

Finding the decimal value of a binary number To find the value of a binary number, follow the example below. Suppose the number is 101101. List the powers of two in row 1, their values in row 2, and the binary numeral positions of the number from right to left in row 3: Base 2 Base 2n value Binary Number

25 32

24 16

23 8

22 4

21 2

20 1

1

0

1

1

0

1

For each 1 in the bottom row, add together the number above it for the decimal value. The value of 101101 is therefore 45: ((1 x 25) + (0 x 24) + (1 x 23) + (1 x 22) + (0 x 21) + (1 x 20)) is equal to (25 + 23 + 22 + 20), which is equal to (32 + 8 + 4 + 1), when solved is equal to 45

Binary addition uses the same principles as decimal addition but with binary digits Adding binary numbers uses the same concepts of place values and carrying if the sum in one place is greater than the largest possible digit. •

In base 10, if the sum exceeds 9 (10 less 1), you perform a carry.

•

In base 2, if the sum exceeds 1 (2 less 1), you perform a carry.

When you learned base 10 addition in elementary school, you most likely began with an addition table. The same table can be applied to base 2. + 0 1 0 0 1 1 1 10 The decimal addition of 1 + 1 = 2 is 10 in binary, which is the binary number for the decimal number 2.

The Binary Addition Table (see above)

Armed with this binary addition table, adding binary values together is easy. Try adding the binary numbers 11 and 1. 1. In the ones bit-place, 1 + 1 = 10 2. The 1 of the 10 is carried to the next bits place, as shown. 3. The addition in the next place 1 + 1 = 10 is then written below, where the 0 is kept in that place and the 1 of that addition is carried over again. 4. For the next place, the addition is assumed as zero: 1 + 0 = 1, and the result, 1, is assigned to that left-most place. The binary sum is the binary number 100, which is equivalent to the decimal number 4.

Decimal number to binary number conversion with the remainder method Given a decimal number, x, do the following steps of computation to get its binary numeral: 1. Divide x by 2. 2. For the first remainder, write it down as the first bit, leaving room to its left for more bits. Otherwise, write the remainder leftover to the immediate left of the previous remainder. 3. If the quotient is not 0, replace x by the quotient and go back to step 1. Otherwise, move on to step 4. 4. The binary numeral is the sequence of remainders read in order from left-to-right.

Remainder method For example, the binary number for the decimal value 53 is 110101 X

Arithmetic computation 53/2 = 26 with remainder 1 26/2 = 13 with remainder of 0 13/2 = 6 with remainder of 1 6/2 = 3 with remainder of 0 3/2 = 1 with remainder of 1 1/2 = 0 with remainder of 1

53 26 13 6 3 1

Quotient

Remainder

26

1

13

01

6

101

3

0101

1

10101

0

110101

To check, convert the binary number of 110101 to decimal: (1 x 25) + (1 x 24) + (0 x 23) + (1 x 22) + (0 x 21) + (1 x 20) = (25 + 24 + 22 + 21) is equal to (32 + 16 + 4 + 1) which is solved to be the decimal number 53.

Decimal number to binary number conversion with the subtraction method Let x be the decimal number you want to convert to binary. 1. Find the largest power of 2 that is less than or equal to x. Suppose it is 2n. Let y = x - 2n. Write 2n on the side. 2. If y is not equal to 0, set x = y and repeat step 1. Otherwise, go to step 3. Repeat until y equals 0. 3. Write the powers of 2 that were set aside in descending order. If an exponent is missing, fill its place with 0. Replace the powers by 1's. It helps to know the powers of 2. Here are the first 17 of them:

n

0 1 2 3 4

5

6

7

8

9

10

11

12

13

14

15

16

2^ n

1 2 4 8 1 6

3 2

6 4

12 8

25 6

51 2

102 4

204 8

409 6

819 2

1638 4

3276 8

6553 6

Subtraction method For example, the binary number for the decimal value 175 is 10101111. X

Arithmetic Computation 175 – 128 = 47 47 – 32 = 15 15 -8 = 7 7–4=3 3–2=1 1–1=0

175 47 15 7 3 1

Y

Power of 2

47 15 7 3 1 0

7 5 3 2 1 0

To check, convert the binary number of 10101111 to decimal: (1 x 27) + (0 x 26) + (1 x 25) + (0 x 24) + (1 x 23) + (1 x 22) + (1 x 21) + (1 x 20) = (27 + 25 + 23 + 22 + 21 + 20) is equal to (128 + 32 + 8 + 4 + 2 + 1) which is solved to be the decimal number 175.

Octal numbers An alternative way to describe is binary numbers is to use the octal number system. Recall that the bases of the decimal number and binary numbers for the first eight values when counting from zero:

Decimal 0 Binary 0

1 1

2 10

3 11

4 100

5 101

6 110

7 111

Each of the decimal values for numbers 0 to 7 is essentially an octal number that corresponds to the respective binary sets of bit-places, where each place is either set with a value either 1 or 0. Therefore, the binary number 101 is also equivalent to the octal number 5. [(1 x 22) + (0 x 21) + (1 x 20) = (22 + 21) = 4 + 1 = 5 ]

Converting binary numbers to octal numerals Generally, an octal numeral is composed from sets of the three binary places of 22, 21, and 20, starting from the right-most set of three bits for a binary number.

For example, convert the binary number 11001: 1. starting from the right-most bit, break it up into sets of three bit-places each – 11 001 2. The first set on the right, 001, is equal to the octal number 1. 3. The second set on the left, 11, can be read as '011', which is equal to the octal number 3. The resulting octal number is 31. Binary Equivalent 000 001 010 011 100 101 110 111

Octal Number 0 1 2 3 4 5 6 7

Converting octal numerals to binary numbers To convert from octal numbers to binary numbers is easy: for each octal number, write the corresponding binary number equivalent, without avoiding any of the bit-places. For example, convert the octal number 16370: 1. Starting from the left-most number, replace each number with the

corresponding binary sets: 1 6 3 7 0 001 110 011 111 000 2. Write the binary sets together as a number. If there is any leading zeroes in the left-most set of bits, they are dropped. The resulting binary is 1110011111000. Binary Equivalent 000 001 010 011 100 101 110 111

Octal Number 0 1 2 3 4 5 6 7...