E2011: Theoretical fundamentals of computer science
Topic 3: Numeral systems
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Outline
1 Introduction
2 Positional numeral systems: decimal system
3 Hexadecimal system
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 2 / 29
Figure: Numerals - from Wikipedia
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 3 / 29
Introduction
Electronic computers/calculators:
analogic computers
digital computers
hybrid computers
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 4 / 29
Introduction
Electronic computers/calculators:
analogic computers
digital computers
hybrid computers
Figure: An analogic computer -
oscilloscope
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 4 / 29
Positional notation
Can be traced back to the work of Archimedes (3rd century BC).
Only in 12th century, the decimal notation was introduced in Europe
(Fibonacci).
123456
4 01235
Index
(position)
10 Radix
(base)
unitstens
hundreds
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 5 / 29
Positional notation
Can be traced back to the work of Archimedes (3rd century BC).
Only in 12th century, the decimal notation was introduced in Europe
(Fibonacci).
123456
4 01235
Index
(position)
10 Radix
(base)
unitstens
hundreds
12345610 = 1 × 105
+ 2 × 104
+ 3 × 103
+ 4 × 102
+ 5 × 101
+ 6 × 100
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 5 / 29
How do we extract the digits from a number (radix 10)?
123456
12345 6
Divide by 10:
quotient remainder
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 6 / 29
Representation
Example (123456)
Sign
0
6
M
SD
1
5
2345
4 1
LSD
6
0
Sign: if present, whether it is a positive or negative integer
MSD: most significant digit
LSD: least significant digit
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 7 / 29
Binary systems (Base-2)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 8 / 29
10100110102 =
= 1 × 29
+ 0 × 28
+ 1 × 27
+ 0 × 26
+ 0 × 25
+ 1 × 24
+ 1 × 23
+ 0 × 22
+ 1 × 21
+ 0 × 20
= 512 + 128 + 16 + 8 + 2
= 66610
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 9 / 29
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 10 / 29
digits (base-10) ←→ bits (base-2)
kilobit (Kb) = 1000 = 103 bits
megabit (Mb) = 1000kb = 106 bits
giga, tera, peta, exa, zetta,...
kibibit = 1024 = 210 bits
mebibit = 1024Kibit = 220 bits
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 11 / 29
8 bits = 1 byte
1 KB = 1024 bytes = 210 bytes = 8192 bits ̸= 1 Kb
1 MB = 1024 KB = 220 bytes
GB, PB, TB, EB...
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 12 / 29
From decimal to binary: 4210 =?2
42/2 −→ quotient: 21 remainder: 0
21/2 −→ quotient: 10 remainder: 1
10/2 −→ quotient: 5 remainder: 0
5/2 −→ quotient: 2 remainder: 1
2/2 −→ quotient: 1 remainder: 0
1/2 −→ quotient: 0 remainder: 1
...and read from last to first remainder:
4210 = 1010102
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 13 / 29
...or quicker (for small numbers):
4210 = 32 + 8 + 2
= 25
+ 23
+ 21
= 1000002 + 10002 + 102 =
= 1010102
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 14 / 29
000002 = 010
000012 = 110
000102 = 210
000112 = 310
001002 = 410
001012 = 510
001102 = 610
001112 = 710
010002 = 810
010012 = 910
010102 = 1010
010112 = 1110
011002 = 1210
011012 = 1310
011102 = 1410
011112 = 1510
100002 = 1610
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 15 / 29
Important properties
with n bits, maximum number representable is
20
+ 21
+ 22
+ · · · + 2n−1
= 2n
− 1
it follows that data is represented with limited precision
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 16 / 29
Bits, bytes, words...
byte (8 bits) is the basic data unit
1 byte is used to represent basic characters (ASCII)
2 bytes are used for extended/international caracters (Unicode)
1 integer value may be represented on 2/4/8/16 bytes: defines the
”word”-size for a given computer → depends on the architecture
short- and long-words have half-/double- the size of the word
there are also ”doublewords”, ”quadwords”
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 17 / 29
Examples
ASCII
- American Standard Code for Information Interchange.
Characters are represented on 8 bits (1 byte):
’A’: 6510 = 4116 = 0100 00012, ’B’: 0100 00102,...
’0’: 4810 = 3016 = 0011 00002,...
etc
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 18 / 29
Examples
32-bit signed integer
Sign
0
31
D
ata
30 0
if ”Sign” is reserved, the range is −231 − 1 to 231 − 1, i.e.
−2, 147, 483, 647 to 2, 147, 483, 647
if ”Sign” is not reserved, the range is 0 to 232 − 1, i.e. 0 to
4, 294, 967, 295
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 19 / 29
Examples
IEEE 754
- technical standard for floating point arithmetic
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 20 / 29
Additions in base-2
13 + 23 =?
carry: 1 1 1 1 1
0 1 1 0 1
+ 1 0 1 1 1
= 1 0 0 1 0 0
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 21 / 29
Binary arithmetic and logical circuits
Example: single-bit adder:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 carry: 1
x y sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 22 / 29
sum = x ⊕ y (XOR)
carry = x · y
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 23 / 29
Bitwise operations
Bitwise operations manipulate strings of bits:
bitwise-NOT: for example, on 4 bits: NOT 7 = 8
(NOT{0111} = 1000)
bitwise-AND: example: 1010&0111 = 0010
bitwise-OR, bitwise-XOR, etc.
test if a number is even/odd: check whether the least significant bit
(index 0) is 0/1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 24 / 29
Bitwise operations
logical shift: insert 0s to the left (shift right) or to the right (shift
left). Example (on 4 bits):
1011 << 1 = 0110 left shift with one position
1011 >> 1 = 0101 right shift with one position
left shift with one position is equivalent to a multiplication by two
right shift with one position is equivalent to a (integer) division by two
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 25 / 29
Bitwise operations
arithmetic shift: insert 0s to the right (shift left) and duplicate the
most significant bit at left (shift right). Example (on 4 bits):
1011 <<< 1 = 0110 left shift with one position
1011 >>> 1 = 1101 right shift with one position
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 26 / 29
Hexadecimal system (Base-16)
need more symbols for hexa-digits: A, B,...,F
000002 = 010 = 016
000012 = 110 = 116
000102 = 210 = 216
000112 = 310 = 316
001002 = 410 = 416
001012 = 510 = 516
001102 = 610 = 616
001112 = 710 = 716
010002 = 810 = 816
010012 = 910 = 916
010102 = 1010 = A16
010112 = 1110 = B16
011002 = 1210 = C16
011012 = 1310 = D16
011102 = 1410 = E16
011112 = 1510 = F16
100002 = 1610 = 1016
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 27 / 29
4 bits correspond to 1 hexa-digit
most of the time, we use hexa notation as it is more compact
in many cases, hexa strings/number are prefixed by 0x to make clear
their meaning
example: HTML color specification R,G,B: #AFA077:
R = 0xAF = 1010 11112 = 10 × 16 + 15 = 175
G = 0xA0 = 1010 00002 = 160
B = 0x77 = 0111 01112 = 119
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 28 / 29
Questions?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 3: Numeral systems 29 / 29