Transcript Computer Science 101

Computer Science 101
Number Systems
Humans

Decimal Numbers (base 10)

Sign-Magnitude (-324)

Decimal Fractions (23.27)

Letters for text
Computers

Binary Numbers (base 2)

Two’s complement and sign-magnitude

Binary fractions and floating point

ASCII codes for characters (A65)
Why binary?

Information is stored in computer via voltage
levels.

Using decimal would require 10 distinct and
reliable levels for each digit.

This is not feasible with reasonable reliability and
financial constraints.

Everything in computer is stored using binary:
numbers, text, programs, pictures, sounds, videos,
...
Decimal: Non-negatives

Base 10

Uses decimal digits: 0,1,2,3,4,5,6,7,8,9

Positional System - position gives power

Example:
3845 = 3x103 + 8x102 + 4x101 + 5x100

Positions:
…543210
Binary: Non-negatives

Base 2

Uses binary digits (bits): 0,1

Positional system

Example:
1101 = 1x23 + 1x22 + 0x21 + 1x20
Conversions

External
(Human)
25
A
Internal
(Computer)
11001
01000001

Humans want to see and enter numbers in
decimal.

Computers must store and compute with
bits.
Binary to Decimal Conversion

Algorithm:
• Expand binary number using positional
scheme.
• Perform computation using decimal arithmetic.

Example:
110012  1x24 + 1x23 + 0x22 + 0x21 +
1x20
= 24 + 23 + 20
= 16 + 8 + 1
= 2510
Decimal to Binary - Algorithm 1

Algorithm:
While N  0 do
Set N to N/2 (whole part)
Record the remainder (1 or 0)
end-of-loop
Set A to remainders in reverse order
Decimal to binary - Example
Example: Convert 32410 to binary
N
Rem
N Rem
324
162
0
5
0
81
0
2
1
40
1
1
0
20
0
0
1
10
0
 32410 = 1010001002

Decimal to Binary - Algorithm 2

Algorithm:
Set A to 0 (all bits 0)
While N  0 do
Find largest P with 2P  N
Set bit in position P of A to 1
Set N to N - 2P
end-of-loop
Decimal to binary - Example

Example: Convert 32410 to binary
N
Power
P
A
324
68
4
0

256
64
4
8
6
2
32410 = 1010001002
100000000
101000000
101000100
Binary Addition
One bit numbers:
+
0
1
0 | 0
1
1 | 1
10
 Example
1111 1
110101 (53)
+ 101101 (45)
1100010 (98)

Overflow

In a given type of computer, the size of
integers is a fixed number of bits.

16 or 32 bits are popular choices

It is possible that addition of two n bit
numbers yields a result requiring n+1 bits.

Overflow is the term for an operation whose
results exceeds the size allowed for a
number.
Negatives: Sign-Magnitude

With a fixed number of bits, say N
• The leftmost bit is used to give the sign
 0 for positive number
 1 for negative number
• The other N-1 bits are for the magnitude

Example: -25 with 8 bit numbers
• Sign: 1 since negative
• Magnitude: 11001 for 25
• 8-bit result: 10011001

Note: This would be 153 as a positive.
Sign-Magnitude: Pros and Cons

Pro:
• Easy to comprehend
• Easy to convert

Con:
• Addition complicated (expensive)
If signs same then
…
else if positive part larger …
• Two representations of 0
Negatives: Two’s complement

With N bit numbers, to compute negative
• Invert all the bits
• Add 1

Example: -25 in 8-bit two’s complement
•
25  00011001
• Invert bits: 11100110
• Add 1:
1
11100111
2’s Complement: Pros and Cons

Con:
• Not so easy to comprehend
• Human must convert negative to identify

Pro:
• Addition is exactly same as for positives
No additional hardware for negatives, and
subtraction.
• One representation of 0
2’s Complement: Examples

Compute negative of -25 (8-bits)
•
•
•
•

We found -25 to be 11100111
Invert bits: 00011000
Add 1:
00011001
Recognize this as 25 in binary
Add -25 and 37 (8-bits)
•
11100111 (-25)
+ 00100101 ( 37)
(1)00001100
• Recognize as 12
Facts about 2’s Complement

Leftmost bit still tells whether number is
positive or negative as with signmagnitude

2’s complement is same as sign magnitude
for positives
2’s complement to decimal (examples)

Assume 8-bit 2’s complement:
• X = 11011001
-X = 00100110 + 1 = 00100111
= 32+4+2+1 = 39 (decimal)
So, X = -39
• X = 01011001
Since X is positive, we have
X = 64+16+8+1 = 89
Ranges for N-bit numbers

Unsigned (positive)

Sign-magnitude

2’s Complement
• 0000…00
or 0
• 1111…11
which is 2N-1
• For N=8, 0 - 255
• 1111…11 which is -(2N-1-1)
• 0111…11 which is 2N-1-1
• For N=8, -127 to 127
• 1000…00 which is -2N-1
• 0111…11 which is 2N-1 - 1
• For N=8, -128 to 127
Overflow Example
(Adds and displays sum)
Overflow - Explanation
We had 2147483645 + 2147483645 = -6
 Why?

• 231 -1 = 147483647 and has 32 bit binary
representation 0111…111. This is largest 2’s
complement 32 bit number.
• 2147483645 would have representation
011111…101.
• When we add this to itself, we get
X = 1111…1010 (overflow)
• So, -X would be 000…0101 + 1 = 00…0110 = 6
• So, X must be -6.
Octal Numbers

Base 8
Digits 0,1,2,3,4,5,6,7

Number does not have so many digits as
binary

Easy to convert to and from binary

Often used by people who need to see the
internal representation of data, programs,
etc.
Octal Conversions

Octal to Binary
• Simply convert each octal digit to a three bit
binary number.
• Example:
5368 = 101 011 1102

Binary to Octal
• Starting at right, group into 3 bit groups
• Convert each group to an octal digit
• Example
110111111010102 = 011 011 111 101 010
= 337528
Hexadecimal
Base 16
Digits 0,…,9,A,B,C,D,E,F
 Hexadecimal  Binary

• Just like Octal, only use 4 bits per digit.
Example:
98C316 = 1001 1000 1100 00112
 Example
110100111010112 = 0011 0100 1110 1011
= 34EB
