Представление чисел в компьютере

Системы счисления

§ 9 . Системы счисления

§ 10 . Позиционные системы счисления

§ 11 . Двоичная система счисления

§ 12. Восьмеричная система счисления

§ 13. Шестнадцатеричная система счисления

§ 14. Другие системы счисления

Системы счисления

§ 9. Системы счисления

Что такое система счисления?

Система счисления — это правила записи чисел с помощью специальных знаков — цифр , а также соответствующие правила выполнения операций с этими числами.

Счёт на пальцах:

Унарная (лат. unus – один) – одна цифра обозначает единицу (1 день, 1 камень, 1 баран, …)

• только натуральные числа
• запись больших чисел – длинная (1 000 000?)

Египетская десятичная система

лотос

– 1

– 10

– 100

– 1 000

– 10 000

– 100 000

– 100 0000

черта

палец

хомут

человек

лягушка

верёвка

= ?

= 1235

2014 = ?

Непозиционные системы счисления

Непозиционная система счисления : значение цифры не зависит от её места в записи числа.

• унарная
• египетская десятичная
• римская
• славянская
• и другие…

« Пираты XX века»

Римская система счисления

I – 1 (палец),

V – 5 (раскрытая ладонь, 5 пальцев) ,

X – 10 (две ладони) ,

L – 50,

C – 100 ( Centum ) ,

D – 500 ( Demimille ) ,

M – 1000 ( Mille )

Спасская башня Московского Кремля

Римская система счисления

Правила :

• (обычно) не ставят больше трех одинаковых цифр подряд если младшая цифра (только одна !) стоит слева от старшей, она вычитается из суммы ( частично непозиционная!)
• (обычно) не ставят больше трех одинаковых цифр подряд
• если младшая цифра (только одна !) стоит слева от старшей, она вычитается из суммы ( частично непозиционная!)

Примеры :

MDC X L I V =

+ 5

– 1

+ 50

– 10

+ 100

+ 500

1000

= 1 644

2389 = 2000 + 300 + 80 + 9

M M

CCC

LXXX

IX

2389 = M M C C C L X X X I X

7

Римская система счисления

MCDLXVII =

MMDCXLIV =

MMMCCLXXII =

CMXXVIII =

Римская система счисления

3768 =

2983 =

1452 =

1999 =

Римская система счисления

• только натуральные числа ( дробные ? отрицательные ?)
• для записи больших чисел нужно вводить новые цифры
• сложно выполнять вычисления

?

Какое максимальное число можно записать?

Славянская система счисления

алфавитная система счисления (непозиционная)

Часы Суздальского Кремля

Системы счисления

§ 10. Позиционные системы счисления

Определения

Позиционная система: значение цифры определяется ее позицией в записи числа.

Алфавит системы счисления — это используемый в ней набор цифр.

Основание системы счисления — это количество цифр в алфавите (мощность алфавита).

Разряд — это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.

Формы записи чисел

развёрнутая форма записи числа

тысячи сотни десятки единицы

разряды

3 2 1 0

= 6 · 10 3 + 3 · 10 2 + 7 · 10 1 + 5 · 10 0

6 3 7 5

6000

300

70

5

Схема Горнера:

6 3 7 5 = ((6  10 + 3)  10 + 7)  10 + 5

• для вычислений не нужно использовать возведение в степень
• удобна при вводе чисел с клавиатуры, начиная с первой

14

Перевод в десятичную систему

Через развёрнутую запись:

=1

разряды : 3 2 1 0

1234 5 = 1  5 3 + 2  5 2 + 3  5 1 + 4  5 0 = 194

основание системы счисления

a 3 a 2 a 1 a 0 = a 3  p 3 + a 2  p 2 + a 1  p 1 + a 0  p 0

разряды : 3 2 1 0

Через схему Горнера:

1234 5 = (( 1  5 + 2 )  5 + 3 )  5 + 4 = 194

a 3 a 2 a 1 a 0 = (( a 3  p + a 2 )  p + a 1 )  p + a 0

Перевод из десятичной в любую

194 = 1234 5 = (( 1  5 + 2 )  5 + 3 )  5 + 4

делится на 5

остаток от деления на 5

a 3 a 2 a 1 a 0 = (( a 3  p + a 2 )  p + a 1 )  p + a 0

a 3 a 2 a 1 = ( a 3  p + a 2 )  p + a 1

остаток от деления на p

частное от деления на p

?

Как найти a 1 ?

?

Как по записи числа в системе с основанием p определить, что оно делится на p 2 ?

Перевод из десятичной в любую

10  5

194

5

1 94 = 1 234 5

190

38

5

35

4

5

7

5

3

?

5

1

Как перевести в систему с основанием 8?

0

2

0

1

Делим число на p , отбрасывая остаток

на каждом шаге, пока не получится 0. Затем надо выписать найденные остатки в обратном порядке.

6 переводим правую часть в десятичную систему решаем уравнение в записи есть цифра 6 , поэтому X 6 переводим правую часть в десятичную систему решаем уравнение 1 0 5 6 x = 5 · X 1 + 6· X 0 = 5 · X + 6 71 = 5 · X + 6 X = 13 " width="640"

17

Задачи

Задача: в некоторой системе счисления число 71 записывается как «5 6 x » ? Определите основание системы счисления X.

71 = 5 6 X

• в записи есть цифра 6 , поэтому X 6 переводим правую часть в десятичную систему решаем уравнение
• в записи есть цифра 6 , поэтому X 6
• переводим правую часть в десятичную систему
• решаем уравнение

1 0

5 6 x

= 5 · X 1 + 6· X 0

= 5 · X + 6

71 = 5 · X + 6

X = 13

5 переводим правую часть в десятичную систему решаем уравнение в записи есть цифра 5, поэтому X 5 переводим правую часть в десятичную систему решаем уравнение 2 1 0 155 x = 1 · X 2 + 5 · X 1 + 5 · X 0 = X 2 + 5 · X + 5 71 = X 2 + 5 · X + 5 X = 6 X = -11 " width="640"

Задачи

Задача: в некоторой системе счисления число 71 записывается как « 15 5 x » ? Определите основание системы счисления X.

71 = 15 5 X

• в записи есть цифра 5, поэтому X 5 переводим правую часть в десятичную систему решаем уравнение
• в записи есть цифра 5, поэтому X 5
• переводим правую часть в десятичную систему
• решаем уравнение

2 1 0

155 x

= 1 · X 2 + 5 · X 1 + 5 · X 0

= X 2 + 5 · X + 5

71 = X 2 + 5 · X + 5

X = 6

X = -11

Задачи

Задача: найдите все основания систем счисления, в которых запись десятичного числа 24 оканчивается на 3.

24 = k · X + 3

21 = k · X

X = 3, 7, 21

Задачи

Задача: найдите все десятичные числа, не превосходящие 40, запись которых в системе счисления с основанием 4 оканчивается на 11.

N = k · 4 2 + 1 · 4 + 1 = k · 16 + 5

При k =0, 1, 2, 3, … получаем

N = 5, 21, 37, 53, …

Задачи

Задача: Все 5-буквенные слова, составленные из букв А, О и У, записаны в алфавитном порядке. Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

5. …

Найдите слово, которое стоит на 140-м месте от начала списка.

А  0

1. 00000

2. 00001

3. 00002

4. 00010

5. …

в троичной системе!

O  1

У  2

на 1-м месте: 0

на 140-м месте: 139

139 = 12011 3

ОУАОО

?

Сколько всего?

Дробные числа

0,6375 = 6·0,1 + 3·0,01 + 7·0,001 + 5·0,0001

Развёрнутая форма записи :

разряды : -1 - 2 -3 -4

0, 6 3 7 5 = 6·10 -1 + 3·10 -2 + 7·10 -3 + 5·10 -4

0, 1 2 3 4 5 = 1 · 5 -1 + 2 · 5 -2 + 3 · 5 -3 + 4· 5 -4

перевод в десятичную систему

Схема Горнера :

0, 6375 = 10 -1 · ( 6 + 10 -1 · ( 3 + 10 -1 · ( 7 + 10 -1 ·5 )))

0,1234 5 = 5 -1 · ( 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 )))

перевод в десятичную систему

Дробные числа: из десятичной в любую

0,1234 5 = 5 -1 · ( 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 )))

5 · ( 0,1234 5 ) = 1 + 5 -1 · ( 2 + 5 -1 · ( 3 + 5 -1 ·4 ))

целая часть

дробная часть

0, a 1 a 2 a 3 a 4 = p -1  ( a 1 + p -1  ( a 2 + p -1  ( a 1 + p -1  a 0 )))

p  ( 0, a 1 a 2 a 3 a 4 ) = a 1 + p -1  ( a 2 + p -1  ( a 1 + p -1  a 0 ))

?

Как найти a 2 ?

Дробные числа: из десятичной в любую

0,9376

10  5

Вычисления

Целая часть

0,9376  5 = 4,688

Дробная часть

4

0,688  5 = 3,44

0,44  5 = 2,2

3

0,688

0,44

2

0,2  5 = 1

0,2

1

0

0,9376 = 0,4321 5

0,3

?

10  5

Что делать?

Дробные числа: из десятичной в любую

10  6

25,375

= 25 + 0, 375

Системы счисления

§ 11. Двоичная система счисления

Двоичная система

Основание (количество цифр): 2

Алфавит : 0, 1

10  2

19

2

19 = 10011 2

18

2

9

8

1

4

2

система счисления

4

1

2

2

2

0

1

2

0

0

0

2  10

1

4 3 2 1 0

разряды

10011 2

= 1 · 2 4 + 0 · 2 3 + 0 · 2 2 + 1 · 2 1 + 1 · 2 0

= 16 + 2 + 1 = 19

Метод подбора

77

10  2

наибольшая степень двойки, которая меньше или равна заданному числу

1

5

13

77

1

4

8

64

1024

512

2 10

256

2 9

128

2 8

64

2 7

32

2 6

2 5

16

8

2 4

2 3

4

2

2 2

2 1

1

2 0

+ 1

1

13

5

+ 8 + …

+ 4 + …

77 = 64 +

Разложение по степеням двойки:

77 = 2 6 + 2 3 + 2 2 + 2 0

77 = 1  2 6 + 0  2 5 + 0  2 4 + 1  2 3 + 1  2 2 + 0  2 1 + 1  2 0

6 5 4 3 2 1 0

разряды

77 = 1001 1 01 2

Перевод из двоичной в десятичную

6 5 4 3 2 1 0

разряды

1001 1 01 2 = 2 6 + 2 3 + 2 2 + 2 0

= 64 + 8 + 4 + 1 = 77

Схема Горнера :

Разряд

6

1

Вычисления

5

4

Результат

1

0

0

1

1  2+ 0

3

2

2

2  2+ 0

1

1

4

4  2+ 1

1

9

9  2+ 1

0

0

19

1

19  2+ 0

38

38  2+ 1

77

Арифметические операции

сложение

вычитание

0+0=0 0+1=1

1+0=1 1+1= 1 0 2

1 + 1 + 1 = 1 1 2

0-0=0 1-1=0

1-0=1 1 0 2 -1=1

перенос

заём





1

1

1

1

1

0 1 1 10 2

0 10 2

1 0 1 1 0 2

+ 1 1 1 0 1 1 2

1 0 0 0 1 0 1 2

– 1 1 0 1 1 2

1

0

0

1

1

0

0

1

1

0

1

0

0

0

2

2

Арифметические операции

101101 2

+ 11111 2

10111 2

+ 101110 2

111011 2

+ 10011 2

111011 2

+ 11011 2

32

Арифметические операции

101101 2

– 11111 2

11011 2

– 110101 2

110101 2

– 11011 2

110011 2

– 10101 2

33

Арифметические операции

умножение

деление

1 0 1 0 1 2

– 1 1 1 2

1 1 1 2

1 0 1 0 1 2

 1 0 1 2

1

1

2

1 1 1 2

– 1 1 1 2

1 0 1 0 1 2

+ 1 0 1 0 1 2

0

1 1 0 1 0 0 1 2

34

Дробные числа

0,8125

10  2

Вычисления

Целая часть

0,8125  2 = 1,625

Дробная часть

1

0,625  2 = 1,25

0,625

1

0,25  2 = 0,5

0,5  2 = 1

0

0,25

0,5

1

0

0,8125 = 0, 1101 2

0, 6 =

0,100110011001 … =

0,(1001) 2

10  2

!

Бесконечное число разрядов!

Дробные числа

• Большинство дробных чисел хранится в памяти с некоторой погрешностью.
• При выполнении вычислений с дробными числами погрешности накапливаются и могут существенно влиять на результат.
• Желательно обходиться без использования дробных чисел, если это возможно.

если то...

если то...

целые,  0

Двоичная система счисления

• нужны только устройства с двумя состояниями
• надёжность передачи данных при помехах
• компьютеру проще выполнять вычисления (умножение сводится сложению и т.п.)

• длинная запись чисел: 1024 = 10000000000 2
• запись однородна (только 0 и 1)

Системы счисления

§ 12. Восьмеричная система счисления

Восьмеричная система счисления

PDP-11, ДВК, СМ ЭВМ, БЭСМ,

БК

Основание : 8

Алфавит : 0, 1 , 2 , 3, 4, 5, 6, 7

10  8

100

8

96

12

8

8

4

1

8

100 = 144 8

0

4

0

1

8  10

2 1 0

разряды

144 8

= 1 · 8 2 + 4 · 8 1 + 4 · 8 0

= 64 + 32 + 4 = 100

Примеры

134 =

75 =

134 8 =

75 8 =

Восьмеричная система счисления

X 10

X 8

0

X 2

0

1

2

000

1

3

2

001

4

3

010

5

4

011

100

5

6

101

6

7

110

7

111

{

{

{

{

Перевод в двоичную систему счисления

10

• трудоёмко
• 2 действия

2

8

8 = 2 3

!

Каждая восьмеричная цифра может быть записана как три двоичных ( триада )!

1725 8 =

00 1

111

010

101 2

1 7 2 5

42

Примеры

3467 8 =

2148 8 =

7352 8 =

1231 8 =

Перевод из двоичной в восьмеричную

1001011101111 2

Шаг 1 . Разбить на триады, начиная справа:

00 1 001 011 101 111 2

Шаг 2 . Каждую триаду записать одной восьмеричной цифрой:

00 1 001 011 101 111 2

1

3

5

7

1

Ответ: 1001011101111 2 = 11357 8

Примеры

101101010010 2 =

11111101011 2 =

1101011010 2 =

Арифметические операции

сложение

1 в перенос

1

1

1

1 в перенос

1 5 6 8

+ 6 6 2 8

6 + 2 = 8 = 8 + 0

5 + 6 + 1 = 1 2 = 8 + 4

1 + 6 + 1 = 8 = 8 + 0

1

0 8

0

4

1 в перенос

Примеры

3 5 3 8

+ 7 3 6 8

1 3 5 3 8

+ 7 7 7 8

47

Арифметические операции

вычитание

заём





4 5 6 8

– 2 7 7 8

( 6 + 8 ) – 7 = 7

(5 – 1 + 8 ) – 7 = 5

(4 – 1 ) – 2 = 1

заём

7 8

1

5

Примеры

1 5 6 8

6 6 2 8

1 1 5 6 8

6 6 2 8

–

–

Системы счисления

§ 13. Шестнадцатеричная система счисления

Шестнадцатеричная система счисления

Основание : 16

Алфавит : 0, 1 , 2 , 3, 4, 5, 6, 7, 8, 9,

F 15

E , 14

D , 13

B , 11

A , 10

C , 12

1 0  16

444

16

444 = 1BC 16

432

27

16

16

12

1

16

С

0

11

0

B

1

16  10

2 1 0

разряды

B

C

= 1 ·16 2 + 11 ·16 1 + 12 ·16 0

= 256 + 176 + 12 = 444

1 BC 16

Примеры

17 1 =

1C 5 16 =

206 =

22B 16 =

Шестнадцатеричная система счисления

X 10

X 16

0

1

0

X 2

0000

1

2

X 10

0001

3

2

X 16

8

0010

3

4

9

X 2

8

4

5

0011

1000

9

5

10

0100

6

1001

6

11

A

0101

7

0110

1010

7

B

12

0111

13

C

1011

D

14

1100

1101

E

15

1110

F

1111

{

{

{

{

Перевод в двоичную систему

• трудоёмко
• 2 действия

10

16

2

16 = 2 4

!

Каждая шестнадцатеричная цифра может быть записана как четыре двоичных ( тетрада )!

7 F1A 16 =

0 1 11

1 1 11

0 001

1010 2

7 F 1 A

Примеры

C73B 16 =

2FE1 16 =

Перевод из двоичной системы

1001011101111 2

Шаг 1 . Разбить на тетрады, начиная справа:

000 1 0010 1110 1111 2

Шаг 2 . Каждую тетраду записать одной шестнадцатеричной цифрой:

000 1 0010 1110 1111 2

1

2

E

F

Ответ: 1001011101111 2 = 12 EF 16

Примеры

1010101101010110 2 =

111100110111110101 2 =

110110110101111110 2 =

Перевод в восьмеричную и обратно

трудоёмко

10

16

8

2

Шаг 1 . Перевести в двоичную систему:

3 DEA 16 =

11 1101 1110 1010 2

Шаг 2 . Разбить на триады (справа):

0 11 110 111 101 010 2

Шаг 3 . Триада – одна восьмеричная цифра:

3 DEA 16 = 36752 8

Примеры

A35 16 =

765 8 =

Арифметические операции

сложение

1

1

A 5 B 16

+ C 7 E 16

10 5 11

+ 12 7 14

1 6 D 9 16

13

9

6

1

1 в перенос

11+14=25= 16 +9

5+7+ 1 = 13 = D 16

10+12=22= 16 +6

1 в перенос

Примеры

С В А 16

+ A 5 9 16

F D В 16

+ A B C 16

Арифметические операции

заём

вычитание





С 5 B 16

– A 7 E 16

1 2 5 11

– 1 0 7 14

1 D D 16

13

1

13

заём

( 11+ 16 ) – 14= 13 = D 16

(5 – 1 )+ 16 – 7= 13 = D 16

( 12 – 1 ) – 10 = 1

Примеры

1 В А 16

– A 5 9 16

Системы счисления

§ 14. Другие системы счисления

Задача Баше о наборе гирь

Как с помощью 4-х гирь взвесить от 0 до 40 кг?

+ 1 гиря на правой чашке

0 гиря снята

– 1 гиря на левой чашке

!

Троичная система!

Веса гирь – степени числа 3:

1 кг, 3 кг, 9 кг, 27 кг

• 1 кг, 3 кг, 9 кг, 27 кг

Пример:

27 кг + 9 кг + 3 кг + 1 кг = 40 кг

• 27 кг + 9 кг + 3 кг + 1 кг = 40 кг

65

Троичная уравновешенная система

ЭВМ «Сетунь» (1958) , Н.П. Брусенцов

Основание : 3

Алфавит : ( «-1» ) , 0, 1

Для N разрядов: всего 3 N значений :

0 + по [ 3 N /2] положительных и отрицательных чисел

• ЭВМ «Сетунь» (1958) , Н.П. Брусенцов Основание : 3 Алфавит : ( «-1» ) , 0, 1 Для N разрядов: всего 3 N значений : 0 + по [ 3 N /2] положительных и отрицательных чисел

уравновешенная система

1

– 4

– 3

= (–1)  3 1 + (–1)  3 0

0

– 2

= (–1)  3 1 + 0  3 0

– 1

1

0

= (–1)  3 1 + 1  3 0

0

1

0 0

= 0  3 1 + (–1)  3 0

2

= 0  3 1 + 0  3 0

0 1

= 0  3 1 + 1  3 0

3

1

4

= 1  3 1 + (–1)  3 0

1 0

= 1  3 1 + 0  3 0

1 1

= 1  3 1 + 1  3 0

1

1

• и положительные, и отрицательные числа
• для изменения знака нужно поменять знаки у всех цифр
• запись короче, чем в двоичной системе

1

1

1

1

• нужны элементы с тремя состояниями

66

Двоично-десятичная система (ДДС)

Десятичные цифры, закодированные в двоичном коде. В inary coded decimal (BCD) .

9024,19 = 1001 0000 0010 0100, 0001 1001 ДДС

9 0 2 4 1 9

101010011,01111 ДДС =

= 000 1 0101 0011, 0111 1 000 ДДС = 153,78

• легко переводить в десятичную систему
• просто умножать и делить на 10
• конечные десятичные дроби записываются точно (аналог ручных расчётов)

• длиннее, чем двоичная запись
• сложнее арифметические операции

Использование – в калькуляторах.

67

Конец фильма

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

[email protected]

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

[email protected]

Источники иллюстраций

• http://www.najboljamamanasvetu.com
• http://www.tissot.ch
• http://www.mindmeister.com
• http://www.antiqueclocksshop.com/
• http://en.wikipedia.org
• http://ru.wikipedia.org
• авторские материалы