Компьютерная арифметика. Операции с целыми числами

1.

Компьютерная
арифметика
1
§ 28. Операции с целыми числами
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

2.

Компьютерная арифметика, 10 класс
2
Сложение и вычитание
!
Операции с положительными и отрицательными
числами выполняются по одинаковым алгоритмам!
+ 5
-9
-4
!
0000
0101
+ 1111 0111
1111 1100
Складываем
столбиком, не
задумываясь о
знаках чисел
Вычитание = сложение с дополнительным кодом
вычитаемого!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

3.

Компьютерная арифметика, 10 класс
3
Переполнение
При сложении двух чисел с одинаковыми знаками может произойти
переполнение.
Сложим десятичные числа со знаком 96 и 33. Их сумма 129 выходит за 8битную сетку. ( Объясните почему? )
Добавим к обоим слагаемым слева еще один старший бит, совпадающим со
знаковым.
!
Если бит S не совпадает с битом S’,
произошло переполнение и результат неверный.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

4.

Компьютерная арифметика, 10 класс
4
Умножение (обычная схема в «столбик»)
× 00001001
9
5
00000101
00001001
+ 00000000
00001001
0000101101 45
8 разрядов
Старший (7-й) разряд равен 0 –
число положительное
1011012=4510
!
× 11110111
-9
5
00000101
11110111
+ 00000000
11110111
10011010011 -45
8 разрядов
Старший (7-й) разряд равен 1 – число
отрицательное, код дополнительный.
Применим алгоритм А2 (инвертируем
все разряды левее последней 1,
знаковый меняем на -)
-01011012=- 4510
Умножение выполняется с помощью сложения и
сдвига.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

5.

Компьютерная арифметика, 10 класс
5
Поразрядные логические операции
Поразрядные (битовые) операции
выполняются с отдельными битами
числа и не влияют на остальные.
?
регистр
Сложение – это поразрядная
операция?
Операция «НЕ» (инверсия, not):
R
1
0
0
1
1
0
1
0
not R
0
1
1
0
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2013
0
1
0
0
1
0
0
0
http://kpolyakov.spb.ru

6.

Компьютерная арифметика, 10 класс
6
Основные понятия
Сброс – это запись в бит нулевого значения.
Установка – это запись в бит единичного значения
Маска – константа, которая определяет область
применения
логической
операции
к
битам
многоразрядного числа.
С помощью маски можно скрывать (защищать) или
открывать для выполнения операции отдельные биты.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

7.

Компьютерная арифметика, 10 класс
7
Логическая операция «И» (and, &)
данные
D
0
1
0
1
маска
Маска – константа, которая
D and M
определяет область применения
0
логической операции к битам
0
многоразрядного числа.
0
AA16 and 6C16 = ?
1
1010 10102 and 0110 11002 = ?
M
0
0
1
1
7
6
5
4
3
2
1
0
D
1
0
1
0
1
0
1
0
AA16
M
0
1
1
0
1
1
0
0
6С16
D and M
0
0
1
0
1
0
0
0
2816
2
!
8
С помощью операции «И» можно сбросить
(установить в ноль) биты, для которых маска равна 0!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

8.

Компьютерная арифметика, 10 класс
8
Логическая операция «ИЛИ» (or, |)
D
0
1
0
1
D or M
0
1
1
1
M
0
0
1
1
AA16 or 6C16 = ?
!
7
6
5
4
3
2
1
0
D
1
0
1
0
1
0
1
0
AA16
M
0
1
1
0
1
1
0
0
6С16
D or M
1
1
1
0
1
1
1
0
EE16
С помощью операции «ИЛИ» можно записать
единицу в биты, для которых маска равна 1!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

9.

Компьютерная арифметика, 10 класс
Операция «исключающее ИЛИ» (xor, ^)
D
0
1
0
1
D xor M
0
1
1
0
M
0
0
1
1
AA16 xor 6C16 = ?
!
7
6
5
4
3
2
1
0
D
1
0
1
0
1
0
1
0
AA16
M
0
1
1
0
1
1
0
0
6С16
D xor M
1
1
0
0
0
1
1
0
C616
С помощью операции «исключающее ИЛИ» можно
инвертировать биты, для которых маска равна 1!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
9

10.

Компьютерная арифметика, 10 класс
Битовые логические операции (итог)
0
0
0
0
1
1
1
1
7
6
5
4
3
2
1
0
R
1
1
1
1
1
F16
0
0
1
916
7
6
5
4
3
2
1
0
1
0
0
1
0
0
0
0
916
016
6
5
4
3
2
1
0
0
0
1
1
0
1
0
0
416
К.Ю. Поляков, Е.А. Ерёмин, 2013
Дано некоторое 8-битное число R.
Записать состояние маски для задач
1-3
1) отключить лампочки 2 и 1, не
трогая остальные
R = R and F916
2) включить лампочки 7 и 4
R = R or 9016
7
316
10
3) изменить состояние лампочек
5, 4 и 2
R = R xor 3416
http://kpolyakov.spb.ru

11.

Компьютерная арифметика, 10 класс
11
Шифрование с помощью xor
Идея: (A xor B) xor B = A
!
Операция «исключающее ИЛИ» обратима, то есть
ее повторное применение восстанавливает исходное
значение!
Рассмотрим пример текста: 2*2=4
Коды символов:
Применим маску, например:
23 = 1716 = 000101112
'2' = 3216 = 001100102
'*' = 2A16 = 001010102
'=' = 3D16 = 001111012
'4' = 3416 = 001101002
К.Ю. Поляков, Е.А. Ерёмин, 2013
'2' 3216 xor 1716 = 2516 '%'
'*' 2A16 xor 1716 = 3D16 '='
'=' 3D16 xor 1716 = 2A16 '*'
'4' 3416 xor 1716 = 2316 '#'
http://kpolyakov.spb.ru

12.

Компьютерная арифметика, 10 класс
12
Шифрование с помощью xor
Маска: 23 = 1716 = 000101112
Исходный текст: 2*2=4
Зашифрованный текст: %=%*#
Расшифровка:
'%' 2516 xor 1716 =
'=' 3D16 xor 1716 =
'*' 2A16 xor 1716 =
'#' 2316 xor 1716 =
!
3216 '2'
2A16 '*'
3D16 '='
3416 '4'
Операция «исключающее ИЛИ» обратима, то есть
ее повторное применение восстанавливает исходное
значение!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

13.

Компьютерная арифметика, 10 класс
13
Логический сдвиг
Влево:
бит
переноса
С
1
Вправо:
1 0 0 1 1 0 1 1
0 0 1 1 0 1 1 0
1 0 0 1 1 0 1 1
0
Запись сдвига:
0 1 0 0 1 1 0 1
0
С
1
shift left
N := N shl 1;
N := N shr 1;
shift right
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

14.

Компьютерная арифметика, 10 класс
14
Логический сдвиг
Влево:
0 0 0 0 1 1 0 0
0 0 0 1 1 0 0 0
12
24
0 0 0 0 1 1 0 0
0 0 0 0 0 1 1 0
12
6
Вправо:
?
Если число нечётное?
Логический сдвиг влево (вправо) – это быстрый
способ умножения (деления без остатка)
положительного числа на 2.
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
Если число отрицательное?
http://kpolyakov.spb.ru

15.

Компьютерная арифметика, 10 класс
15
Арифметический сдвиг (вправо)
–12 1 1 1 1 0 1 0 0
–6
?
1 1 1 1 1 0 1 0
С
0
Если число нечётное?
Примеры:
20 10
15 7
–20 –10
–15 –8
11 5
3 1
–11 –6
–3 –2
1 0
–1 –1
К.Ю. Поляков, Е.А. Ерёмин, 2013
Арифметический сдвиг
вправо – деление на 2
нацело с округлением
«вниз» (к ближайшему
меньшему целому).
http://kpolyakov.spb.ru

16.

Компьютерная арифметика, 10 класс
16
Циклический сдвиг
Влево:
1 0 0 1 1 0 1 1
0 0 1 1 0 1 1 1
Вправо:
1 0 0 1 1 0 1 1
1 1 0 0 1 1 0 1
!
Циклический сдвиг предназначен для
последовательного просмотра битов без
потери данных.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

17.

Компьютерная арифметика, 10 класс
17
Пример
Задача: в целой переменной N (32 бита) закодирована
информация о цвете пикселя в RGB:
24 23
31
0
16 15
R
87
G
0
B
Записать в переменные R, G, B составляющие цвета.
Вариант 1:
1. Обнулить все биты, кроме G.
Маска для выделения G: 0000FF0016
2. Сдвинуть вправо так, чтобы число G передвинулось в
младший байт.
G:=(N and 0000FF00) shr 8
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

18.

Компьютерная арифметика, 10 класс
18
Пример
24 23
31
0
16 15
R
87
0
G
B
Вариант 2:
1. Сдвинуть вправо так, чтобы число G передвинулось в
младший байт.
2. Обнулить все биты, кроме G.
Маска для выделения G: 000000FF16
G:=(N shr 8) and 000000FF
?
Как решить, используя только сдвиги?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

19.

Компьютерная арифметика, 10 класс
19
Задание
24 23
31
0
16 15
R
87
G
0
B
Используя приведенные алгоритмы, записать в переменные R, B
составляющие цвета.
R:=
B:=
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

20.

Компьютерная арифметика, 10 класс
Домашнее задание
20
Выучить конспект ( Учебник п. 28).
Выполнить письменно №1, 2 (стр 249)
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru