Princeton University

Computer Science 217: Introduction to Programming Systems

Number Systems
and
Number Representation

Q: Why do computer programmers

confuse Christmas and Halloween?
A: Because 25 Dec = 31 Oct

1
Goals of this Lecture

Help you learn (or refresh your memory) about:

• The binary, hexadecimal, and octal number systems
• Finite representation of unsigned integers
• Finite representation of signed integers
• Finite representation of rational numbers (if time)

Why?
• A power programmer must know number systems and data
representation to fully understand C’s primitive data types

Primitive values and

the operations on them
2
Agenda

Number Systems
Finite representation of unsigned integers
Finite representation of signed integers
Finite representation of rational numbers (if time)

3
The Decimal Number System
Name
• “decem” (Latin) ⇒ ten

Characteristics
• Ten symbols
•0 1 2 3 4 5 6 7 8 9
• Positional
• 2945 ≠ 2495
• 2945 = (2*103) + (9*102) + (4*101) + (5*100)

(Most) people use the decimal number system

Why?

4
The Binary Number System
binary
adjective: being in a state of one of two mutually exclusive conditions such as
on or off, true or false, molten or frozen, presence or absence of a
signal. From Late Latin bīnārius (“consisting of two”).

Characteristics
• Two symbols
•0 1
• Positional
• 1010B ≠ 1100B

Most (digital) computers use the binary number system

Why?
Terminology
• Bit: a binary digit
• Byte: (typically) 8 bits
5
Decimal-Binary Equivalence
Decimal Binary Decimal Binary
0 0 16 10000
1 1 17 10001
2 10 18 10010
3 11 19 10011
4 100 20 10100
5 101 21 10101
6 110 22 10110
7 111 23 10111
8 1000 24 11000
9 1001 25 11001
10 1010 26 11010
11 1011 27 11011
12 1100 28 11100
13 1101 29 11101
14 1110 30 11110
15 1111 31 11111
... ...
6
Decimal-Binary Conversion

Binary to decimal: expand using positional notation

100101B = (1*25)+(0*24)+(0*23)+(1*22)+(0*21)+(1*20)
= 32 + 0 + 0 + 4 + 0 + 1
= 37

7
Integer
Decimal-Binary Conversion
Integer
Binary to decimal: expand using positional notation
100101B = (1*25)+(0*24)+(0*23)+(1*22)+(0*21)+(1*20)
= 32 + 0 + 0 + 4 + 0 + 1
= 37

These are integers

They exist as their pure selves
no matter how we might choose
to represent them with our
fingers or toes

8
Integer-Binary Conversion
Integer to binary: do the reverse
• Determine largest power of 2 ≤ number; write template
37 = (?*25)+(?*24)+(?*23)+(?*22)+(?*21)+(?*20)

• Fill in template

37 = (1*25)+(0*24)+(0*23)+(1*22)+(0*21)+(1*20)
-32
5
-4
1 100101B
-1
0

9
Integer-Binary Conversion
Integer to binary shortcut
• Repeatedly divide by 2, consider remainder

37 / 2 = 18 R 1
18 / 2 = 9 R 0
9 / 2 = 4 R 1 Read from bottom
4 / 2 = 2 R 0 to top: 100101B
2 / 2 = 1 R 0
1 / 2 = 0 R 1

10
The Hexadecimal Number System
Name
• “hexa” (Greek) ⇒ six
• “decem” (Latin) ⇒ ten

Characteristics
• Sixteen symbols
•0 1 2 3 4 5 6 7 8 9 A B C D E F
• Positional
• A13DH ≠ 3DA1H

Computer programmers often use the hexadecimal number

system
Why?

11
Decimal-Hexadecimal Equivalence
Decimal Hex Decimal Hex Decimal Hex
0 0 16 10 32 20
1 1 17 11 33 21
2 2 18 12 34 22
3 3 19 13 35 23
4 4 20 14 36 24
5 5 21 15 37 25
6 6 22 16 38 26
7 7 23 17 39 27
8 8 24 18 40 28
9 9 25 19 41 29
10 A 26 1A 42 2A
11 B 27 1B 43 2B
12 C 28 1C 44 2C
13 D 29 1D 45 2D
14 E 30 1E 46 2E
15 F 31 1F 47 2F
... ...
12
Integer-Hexadecimal Conversion
Hexadecimal to integer: expand using positional notation
25H = (2*161) + (5*160)
= 32 + 5
= 37

Integer to hexadecimal: use the shortcut

37 / 16 = 2 R 5 Read from bottom

2 / 16 = 0 R 2 to top: 25H

13
Binary-Hexadecimal Conversion
Observation: 161 = 24
• Every 1 hexadecimal digit corresponds to 4 binary digits

Binary to hexadecimal

1010000100111101B
Digit count in binary number
A 1 3 DH not a multiple of 4 ⇒
pad with zeros on left
Hexadecimal to binary
A 1 3 DH Discard leading zeros
1010000100111101B from binary number if
appropriate

Is it clear why programmers

often use hexadecimal?
14
The Octal Number System
Name
• “octo” (Latin) ⇒ eight

Characteristics
• Eight symbols
•0 1 2 3 4 5 6 7
• Positional
• 1743O ≠ 7314O

Computer programmers often use the octal number system

Why?

(So does Mickey Mouse!)

15
Agenda

Number Systems
Finite representation of unsigned integers
Finite representation of signed integers
Finite representation of rational numbers (if time)

16
Unsigned Data Types: Java vs. C
Java has type:
• int
• Can represent signed integers

C has type:
• signed int
• Can represent signed integers
• int
• Same as signed int
• unsigned int
• Can represent only unsigned integers

To understand C, must consider representation of both

unsigned and signed integers
17
Representing Unsigned Integers
Mathematics
• Range is 0 to ∞

Computer programming
• Range limited by computer’s word size
• Word size is n bits ⇒ range is 0 to 2n – 1
• Exceed range ⇒ overflow

CourseLab computers
• n = 64, so range is 0 to 264 – 1 (huge!)

Pretend computer
• n = 4, so range is 0 to 24 – 1 (15)

Hereafter, assume word size = 4

• All points generalize to word size = 64, word size = n
18
Representing Unsigned Integers
On pretend computer Unsigned
Integer Rep
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
19
Adding/subtracting binary numbers
Addition

0011
1010
Subtraction Subtraction

1010 0011
0111 1010

20
Adding Unsigned Integers
Addition
1
3 0011B Start at right column
+ 10 + 1010B Proceed leftward
-- ---- Carry 1 when necessary
13 1101B

1
7 0111B Beware of overflow
+ 10 + 1010B
-- ----
1 0001B

How would you

detect overflow
Results are mod 24 programmatically?

21
Subtracting Unsigned Integers
Subtraction

Start at right column

111
10 1010B Proceed leftward
- 7 - 0111B Borrow when necessary
-- ----
3 0011B

1
3 0011B Beware of overflow
- 10 - 1010B
-- ----
9 1001B
How would you
detect overflow
Results are mod 24 programmatically?

22
Shifting Unsigned Integers
Bitwise right shift (>> in C): fill on left with zeros
10 >> 1 ⇒ 5
What is the effect
1010B 0101B
arithmetically?
10 >> 2 ⇒ 2 (No fair looking ahead)

1010B 0010B

Bitwise left shift (<< in C): fill on right with zeros

5 << 1 ⇒ 10
0101B 1010B What is the effect
arithmetically?
3 << 2 ⇒ 12 (No fair looking ahead)
0011B 1100B
Results are mod 24
23
Other Operations on Unsigned Ints
Bitwise NOT (~ in C)
• Flip each bit

~10 ⇒ 5
1010B 0101B

Bitwise AND (& in C)

• Logical AND corresponding bits

10 1010B
& 7 & 0111B Useful for setting
-- ----
2 0010B
selected bits to 0

24
Other Operations on Unsigned Ints
Bitwise OR: (| in C)
• Logical OR corresponding bits
10 1010B
| 1 | 0001B Useful for setting
-- ----
11 1011B
selected bits to 1

Bitwise exclusive OR (^ in C)
• Logical exclusive OR corresponding bits

10 1010B
^ 10 ^ 1010B x ^ x sets
-- ----
0 0000B
all bits to 0

25
Aside: Using Bitwise Ops for Arith
Can use <<, >>, and & to do some arithmetic efficiently
x * 2y == x << y
Fast way to multiply
• 3*4 = 3*22 = 3<<2 ⇒ 12
by a power of 2
x / 2y == x >> y
Fast way to divide
• 13/4 = 13/22 = 13>>2 ⇒ 3
unsigned by power of 2
x % 2y == x & (2y-1)
• 13%4 = 13%22 = 13&(22-1) Fast way to mod
= 13&3 ⇒ 1 by a power of 2

13 1101B
& 3 & 0011B
-- ----
1 0001B

26
Aside: Example C Program
#include <stdio.h>
#include <stdlib.h>
int main(void)
{ unsigned int n;
unsigned int count;
printf("Enter an unsigned integer: ");
if (scanf("%u", &n) != 1)
{ fprintf(stderr, "Error: Expect unsigned int.\n");
exit(EXIT_FAILURE);
}
for (count = 0; n > 0; n = n >> 1)
count += (n & 1);
printf("%u\n", count);
return 0;
} How could this be
What does it expressed more
write? succinctly?
27
Aside from the aside…
Personally, I wouldn’t put the (count=0) in the for(;;) initializer,
for (count = 0; n > 0; n = n >> 1)
count += (n & 1);

because it’s not really part of the loop iterator. In this case,
the iterator is n, which (in this case) happens to be already
initialized.

So it’s perhaps more straightforward to write,

count = 0;
for ( ; n > 0; n = n >> 1)
count += (n & 1);

28
Agenda

Number Systems
Finite representation of unsigned integers
Finite representation of signed integers
Finite representation of rational numbers (if time)

29
Signed Magnitude
Integer Rep
-7 1111
-6 1110
-5 1101
-4 1100 Definition
-3 1011
-2 1010
High-order bit indicates sign
-1 1001 0 ⇒ positive
-0 1000 1 ⇒ negative
0 0000
1 0001
Remaining bits indicate magnitude
2 0010 1101B = -101B = -5
3 0011 0101B = 101B = 5
4 0100
5 0101
6 0110
7 0111
30
Signed Magnitude (cont.)
Integer Rep
-7 1111
-6 1110 Computing negative
-5 1101 neg(x) = flip high order bit of x
-4 1100
-3 1011
neg(0101B) = 1101B
-2 1010 neg(1101B) = 0101B
-1 1001
-0 1000 Pros and cons
0 0000
1 0001 + easy for people to understand
2 0010 + symmetric
3 0011 - two representations of zero
4 0100
5 0101 - can’t use the same “add” algorithm for
6 0110 both signed and unsigned numbers
7 0111
31
Ones’ Complement
Integer Rep
-7 1000
-6 1001
-5 1010
-4 1011 Definition
-3 1100
-2 1101
High-order bit has weight -7
-1 1110 1010B = (1*-7)+(0*4)+(1*2)+(0*1)
-0 1111 = -5
0 0000 0010B = (0*-7)+(0*4)+(1*2)+(0*1)
1 0001
2 0010 = 2
3 0011
4 0100
5 0101
6 0110
7 0111
32
Ones’ Complement (cont.)
Integer Rep Computing negative
-7 1000 neg(x) = ~x
-6 1001
-5 1010
neg(0101B) = 1010B
-4 1011 neg(1010B) = 0101B
-3 1100
-2 1101 Computing negative (alternative)
-1 1110
neg(x) = 1111B - x
-0 1111
0 0000 neg(0101B) = 1111B – 0101B
1 0001 = 1010B
2 0010 neg(1010B) = 1111B – 1010B
3 0011
4 0100 = 0101B
Pros and cons
5 0101
+ symmetric
6 0110
− two reps of zero
7 0111
− can’t use the same “add” algorithm for both signed
and unsigned numbers 33
Two’s Complement
Integer Rep
-8 1000
-7 1001
-6 1010
-5 1011 Definition
-4 1100
-3 1101
High-order bit has weight -8
-2 1110 1010B = (1*-8)+(0*4)+(1*2)+(0*1)
-1 1111 = -6
0 0000 0010B = (0*-8)+(0*4)+(1*2)+(0*1)
1 0001
2 0010 = 2
3 0011
4 0100
5 0101
6 0110
7 0111
34
Two’s Complement (cont.)
Integer Rep
-8 1000
-7 1001 Computing negative
-6 1010 neg(x) = ~x + 1
-5 1011 neg(x) = onescomp(x) + 1
-4 1100
-3 1101
neg(0101B) = 1010B + 1 = 1011B
-2 1110 neg(1011B) = 0100B + 1 = 0101B
-1 1111
0 0000
1 0001 Pros and cons
2 0010 - not symmetric
3 0011
4 0100 + one representation of zero
5 0101 + same algorithm adds unsigned numbers
6 0110 or signed numbers
7 0111
35
Two’s Complement (cont.)

Almost all computers use two’s complement to represent

signed integers
Why?
• Arithmetic is easy
• Will become clear soon

Hereafter, assume two’s complement representation of

signed integers

36
Adding Signed Integers
pos + pos pos + pos (overflow)
11 111
3 0011B 7 0111B
+ 3 + 0011B + 1 + 0001B
-- ---- -- ----
6 0110B -8 1000B

pos + neg
1111 How would you
3 0011B
+ -1 + 1111B
detect overflow
-- ---- programmatically?
2 10010B

neg + neg neg + neg (overflow)

11 1 1
-3 1101B -6 1010B
+ -2 + 1110B + -5 + 1011B
-- ---- -- ----
-5 11011B 5 10101B 37
Subtracting Signed Integers

Perform subtraction Compute two’s comp

with borrows or and add

1
22
3 0011B 3 0011B
- 4 - 0100B + -4 + 1100B
-- ---- -- ----
-1 1111B -1 1111B

111
-5 1011B -5 1011
- 2 - 0010B + -2 + 1110
-- ---- -- ----
-7 1001B -7 11001

38
Negating Signed Ints: Math
Question: Why does two’s comp arithmetic work?
Answer: [–b] mod 24 = [twoscomp(b)] mod 24

[–b] mod 24
= [24 – b] mod 24
= [24 – 1 - b + 1] mod 24
= [(24 – 1 - b) + 1] mod 24
= [onescomp(b) + 1] mod 24
= [twoscomp(b)] mod 24

See Bryant & O’Hallaron book for much more info

39
Subtracting Signed Ints: Math

And so:
[a – b] mod 24 = [a + twoscomp(b)] mod 24

[a – b] mod 24
= [a + 24 – b] mod 24
= [a + 24 – 1 – b + 1] mod 24
= [a + (24 - 1 – b) + 1] mod 24
= [a + onescomp(b) + 1] mod 24
= [a + twoscomp(b)] mod 24

See Bryant & O’Hallaron book for much more info

40
Shifting Signed Integers
Bitwise left shift (<< in C): fill on right with zeros
3 << 1 ⇒ 6
0011B 0110B What is the effect
arithmetically?
-3 << 1 ⇒ -6
1101B -1010B

Bitwise arithmetic right shift: fill on left with sign bit

6 >> 1 ⇒ 3
0110B 0011B What is the effect
arithmetically?
-6 >> 1 ⇒ -3
1010B 1101B
Results are mod 24
41
Shifting Signed Integers (cont.)
Bitwise logical right shift: fill on left with zeros
6 >> 1 ⇒ 3
0110B 0011B What is the effect
arithmetically???
-6 >> 1 ⇒ 5
1010B 0101B

In C, right shift (>>) could be logical or arithmetic

• Not specified by C90 standard
• Compiler designer decides

Best to avoid shifting signed integers

(if you must shift signed integers, make sure you’re on a 2’s complement
machine, and do a bitwise-and after shifting)
(Java does this better, with two operators: >> >>> )
42
Shifting Signed Integers (cont.)

Is it after 1980?
OK, then we’re surely
two’s complement

(if you must shift signed integers, make sure you’re on a 2’s complement
machine, and do a bitwise-and after shifting)

43
Other Operations on Signed Ints
Bitwise NOT (~ in C)
• Same as with unsigned ints

Bitwise AND (& in C)

• Same as with unsigned ints

Bitwise OR: (| in C)
• Same as with unsigned ints

Bitwise exclusive OR (^ in C)
• Same as with unsigned ints

Best to avoid with signed integers

44
Agenda

Number Systems
Finite representation of unsigned integers
Finite representation of signed integers
Finite representation of rational numbers (if time)

45
Rational Numbers

Mathematics
• A rational number is one that can be expressed
as the ratio of two integers
• Unbounded range and precision

Computer science
• Finite range and precision
• Approximate using floating point number
• Binary point “floats” across bits

46
IEEE Floating Point Representation
Common finite representation: IEEE floating point
• More precisely: ISO/IEEE 754 standard

Using 32 bits (type float in C):

• 1 bit: sign (0⇒positive, 1⇒negative)
• 8 bits: exponent + 127
• 23 bits: binary fraction of the form 1.ddddddddddddddddddddddd

Using 64 bits (type double in C):

• 1 bit: sign (0⇒positive, 1⇒negative)
• 11 bits: exponent + 1023
• 52 bits: binary fraction of the form
1.dddddddddddddddddddddddddddddddddddddddddddddddddddd

47
Floating Point Example

11000001110110110000000000000000
Sign (1 bit):
• 1 ⇒ negative 32-bit representation
Exponent (8 bits):
• 10000011B = 131
• 131 – 127 = 4

Fraction (23 bits): also called “mantissa”

• 1.10110110000000000000000B
• 1 + (1*2-1)+(0*2-2)+(1*2-3)+(1*2-4)+(0*2-5)+(1*2-
6)+(1*2-7) = 1.7109375

Number:
• -1.7109375 * 24 = -27.375
48
When was floating-point invented?
Answer: long before computers!
mantissa
noun
decimal part of a logarithm, 1865, from Latin mantisa “a worthless
addition, makeweight,” perhaps a Gaulish word introduced into Latin via
Etruscan (cf. Old Irish meit, Welsh maint "size").
Floating Point Warning
Decimal number system can Decimal Rational
Approx Value
represent only some rational .3 3/10
numbers with finite digit count .33 33/100
.333 333/1000
• Example: 1/3 ...

Binary number system can Binary Rational

Approx Value
represent only some rational 0.0 0/2
numbers with finite digit count 0.01 1/4
0.010 2/8
• Example: 1/5 0.0011 3/16
0.00110 6/32
0.001101 13/64
Beware of roundoff error 0.0011010 26/128
• Error resulting from inexact 0.00110011 51/256
...
representation
• Can accumulate

50
Summary

The binary, hexadecimal, and octal number systems

Finite representation of unsigned integers
Finite representation of signed integers
Finite representation of rational numbers

Essential for proper understanding of

• C primitive data types
• Assembly language
• Machine language

51