Операции в языке С (продолжение)

Сентябрь 7, 2022

Главная
Алгебра
Операции в языке С (продолжение)

Содержание

2. Краткое содержание предыдущей серии Как в ассемблере происходит сравнение? Как используется результат сравнения? Что такое «условное
3. Краткое содержание этой серии О магии Операции в языке С (продолжение) О-нотация
4. Что такое «магия»? В широком смысле – это «что-то непонятное». Строгой классификации не существует. Условно: белая
5. Пример «белой магии» Функция sin. Что возвращает sin? Синус угла. А как она его вычисляет? Правильно.
6. Пример «черной магии» Очень сложно понять, что делает эта программа и как она это делает.
7. Причины «магии» «Индуизм» Ручная оптимизация Магические числа Обфускация (намеренное ухудшение читаемости кода) Недокументированные и малоизвестные особенности
8. «Индуизм» («индусский код») Не индуизм: if( i > 0 && i Индуизм: if( i.toString().length() == 2
9. «Магические числа» Это численные константы, смысл которых не ясен. #define SPEED_MAX 59 void setSpeed(int speed) {
10. Как сделать черную магию белой? // Быстрый вариант функции 1/sqrt. // Быстр при аппаратной поддержке плавающей
11. Что такое интерфейс? Интерфейс – набор входов и выходов черного ящика; их свойства, возможные диапазоны и
12. Интерфейсы double sin( double angleInRadians ); int work( int a, int b, int * с );
13. Хороший интерфейс делает черную магию белой!
14. Операции в языке С (продолжение) Логические Битовые
15. Логические операции ! – логическое отрицание && - логическое И || - логическое ИЛИ Т.к. тип
16. Логическое отрицание - ! Результат выражения !A равен нулю, если А не равно нулю и равен
17. Логическое ИЛИ - || Результат выражения А || B равен нулю, только если оба аргумента равны
18. Логическое И - && Результат выражения А && B равен единице, только если оба аргумента не
19. Логические операции в ассемблере Их нет! Есть только битовые. Все операции, которые называются «logical» в тех.
20. Битовые операции языка С ~ - битовая инверсия | - битовое ИЛИ & - битовое И
21. Битовая инверсия - ~ При битовой инверсии каждый бит двоичного представления аргумента меняется на противоположный (инвертируется).
22. Битовое ИЛИ - | Результатом битового ИЛИ будет число, каждый бит которого является результатом булевой операции
23. Битовое И - & Результатом битового И будет число, каждый бит которого является результатом булевой операции
24. Битовое исключающее ИЛИ (XOR) - ^ Если значение одного бита у аргументов разное – то результат
26. Сдвиги Сдвиги бывают: «просто» сдвиги – они же «логические» (без учета знака) арифметические (с учетом знака)
27. Сдвиг влево -
28. Сдвиг вправо - >>
29. Примеры сюрпризов int a = -1 int a = 1 int a = 1 int a
30. Сюрприз в сюрпризе Описания сдвигов отрицательных чисел появились в стандарте слишком поздно. Программисты успели написать достаточно
31. Рассмотрим два алгоритма сортировки Сортировка пузырьком Сортировка выбором
32. Какой из них быстрее? А если взять другой массив? А если взять другой компьютер? А если
33. Как узнать, какой алгоритм быстрее? Написать программу и запустить? но ее можно написать с ошибками на
34. Теоретический анализ? Какая самая долгая операция в алгоритме? Какая операция выполняется наибольшее количество раз? От чего
35. Теоретический анализ?
36. Теоретический анализ?
37. Теоретический анализ? Абстрагироваться от «железа» Абстрагироваться от входных данных Получается т.н. «О-нотация» (Big-Oh notation): Время работы
39. Скачать презентацию

Слайд 2

Краткое содержание предыдущей серии
Как в ассемблере происходит сравнение?
Как используется результат сравнения?
Что

такое «условное исполнение»?
Как в ассемблере осуществляется ветвление?

Слайд 3

Краткое содержание этой серии
О магии
Операции в языке С (продолжение)
О-нотация

Слайд 4

Что такое «магия»?
В широком смысле – это «что-то непонятное».
Строгой классификации

не существует.
Условно:
белая магия – результат действия полностью понятен, но не понятен механизм
черная магия – результат действия понятен не полностью или вообще ничего непонятно

Слайд 5

Пример «белой магии»
Функция sin. Что возвращает sin?
Синус угла.
А как она

его вычисляет?
Правильно.
Если вас устраивает результат «белой магии» (точность, скорость и т.д.), то понимать ее механизм не обязательно.

Слайд 6

Пример «черной магии»
Очень сложно понять, что делает эта программа и как

она это делает.

Слайд 7

Причины «магии»
«Индуизм»
Ручная оптимизация
Магические числа
Обфускация (намеренное ухудшение читаемости кода)
Недокументированные и малоизвестные особенности

чего-либо
Соревнования волшебников

Слайд 8

«Индуизм» («индусский код»)
Не индуизм:
if( i > 0 && i < 100

)

Индуизм:
if( i.toString().length() == 2 )

Стремление писать код кривым, неочевидным,
неестественным способом (жаргонное обозначение).

Слайд 9

«Магические числа»
Это численные константы, смысл которых не ясен.
#define SPEED_MAX 59
void setSpeed(int

speed)
{
if(speed > SPEED_MAX)
return;
...
}

void setSpeed(int speed)
{
if(speed > 59)
return;
...
}

Слайд 10

Как сделать черную магию белой?
// Быстрый вариант функции 1/sqrt.
// Быстр

при аппаратной поддержке плавающей арифметики
float fastInverseSqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}

Слайд 11

Что такое интерфейс?
Интерфейс – набор входов и выходов черного ящика; их

свойства, возможные диапазоны и т.д.
В зависимости от области интерфейс может быть разным.

Слайд 12

Интерфейсы
double sin( double angleInRadians );
int work( int a, int b, int

* с );
// зависит от трех глобальных переменных
// возвращает значение -1, если нет ошибок
// переменная с не нужна уже второй год,
// но ее забывают убрать

Хороший интерфейс:

Плохой интерфейс:

Слайд 13

Хороший интерфейс делает черную магию белой!

Слайд 14

Операции в языке С (продолжение)
Логические
Битовые

Слайд 15

Логические операции
! – логическое отрицание
&& - логическое И
|| - логическое ИЛИ
Т.к.

тип bool был введен только в С99, все логические операции используют тип int.
Поэтому для них 0 – это ложь, а любое другое число – истина.

Слайд 16

Логическое отрицание - !
Результат выражения !A равен нулю, если А не

равно нулю
и равен единице, если А равно нулю.
Выражение !A эквивалентно выражению 0==A.

Слайд 17

Логическое ИЛИ - ||
Результат выражения А || B равен нулю, только

если оба аргумента равны нулю, во всех остальных случаях результат равен единице.

Слайд 18

Логическое И - &&
Результат выражения А && B равен единице, только

если оба аргумента не равны нулю, во всех остальных случаях результат равен нулю.

Слайд 19

Логические операции в ассемблере
Их нет! Есть только битовые.
Все операции, которые называются

«logical» в тех. описании, являются битовыми.
Логические операции языка С превращаются в несколько ассемблерных команд.

Слайд 20

Битовые операции языка С
~ - битовая инверсия
| - битовое ИЛИ
& -

битовое И
^ - битовое исключающее или (XOR)
>> - сдвиг вправо
<< - сдвиг влево
Все битовые операции выполняются над двоичными представлениями чисел.
В языке С битовые операции определены только для целых чисел!

Слайд 21

Битовая инверсия - ~
При битовой инверсии каждый бит двоичного представления аргумента

меняется на противоположный (инвертируется).
Размер (в байтах) результата операции равен размеру аргумента, поэтому результат зависит от типа!
Примеры:
uint8_t A = 5; // A = 0000 01012 = 510
A = ~A; // A = 1111 10102 = 25010
uint16_t B = 5; // B = 0000 0000 0000 01012 = 510
B = ~B; // B = 1111 1111 1111 10102 = 6553010

Слайд 22

Битовое ИЛИ - |
Результатом битового ИЛИ будет число, каждый бит которого

является результатом булевой операции ИЛИ между соответствующими битами аргументов.
Коротко: если бит равен 1 в любом из аргументов – он равен 1 в результате.
A |= B эквивалентно A = A | B.
Битовое ИЛИ удобно использовать для установки отдельных битов в единицу: a |= 1;

Слайд 23

Битовое И - &
Результатом битового И будет число, каждый бит которого

является результатом булевой операции И между соответствующими битами аргументов.
Коротко: если бит равен 0 в любом из аргументов – он равен 0 в результате.
A &= B эквивалентно A = A & B.
Битовое И удобно использовать для обнуления отдельных битов:
a &= ~1;

Слайд 24

Битовое исключающее ИЛИ (XOR) - ^
Если значение одного бита у аргументов

разное – то результат равен 1.
A ^= B эквивалентно A = A ^ B.
Битовое исключающее ИЛИ удобно использовать для инверсии отдельных битов:
a ^= 1;

Слайд 25

Слайд 26

Сдвиги
Сдвиги бывают:
«просто» сдвиги – они же «логические» (без учета знака)
арифметические (с

учетом знака)
циклические
Какие же сдвиги в языке С?
Не циклические.

Слайд 27

Сдвиг влево - <<

Слайд 28

Сдвиг вправо - >>

Слайд 29

Примеры сюрпризов
int a = -1 << 1; - undefined behaviour
int a

= 1 << 100; - undefined behaviour
int a = 1 << -2; - undefined behaviour
int a = 1 >> -3; - undefined behaviour
int a = -1 >> 4; - implementation defined

Слайд 30

Сюрприз в сюрпризе
Описания сдвигов отрицательных чисел появились в стандарте слишком поздно.
Программисты

успели написать достаточно кода, где такие сдвиги используются!
Зачем?
Для получения битовых масок с заданным числом нулей удобно сдвигать -1 (если он в доп. коде)
Но так делать не надо! Сдвигайте лучше ~0u

Слайд 31

Рассмотрим два алгоритма сортировки
Сортировка пузырьком
Сортировка выбором

Слайд 32

Какой из них быстрее?
А если взять другой массив?
А если взять другой

компьютер?
А если массив будет гораздо, гораздо больше?

Слайд 33

Как узнать, какой алгоритм быстрее?
Написать программу и запустить?
но ее можно написать

с ошибками
на разных компьютерах скорость будет разной
на разных исходных данных скорость будет разной
на разных запусках скорость может быть разной!

Слайд 34

Теоретический анализ?
Какая самая долгая операция в алгоритме?
Какая операция выполняется наибольшее количество

раз?
От чего зависит это количество?

Слайд 35

Теоретический анализ?

Слайд 36

Теоретический анализ?

Слайд 37

Теоретический анализ?
Абстрагироваться от «железа»
Абстрагироваться от входных данных
Получается т.н. «О-нотация» (Big-Oh notation):
Время

работы алгоритма выражается как функция от размера входных данных N
Игнорируются константные коэффициенты
Остается только старший порядок
Очень грубое объяснение! Подробнее см. «алгоритмическая сложность», «теория алгоритмов»

Операции в языке С (продолжение)

Содержание

Краткое содержание предыдущей серииКак в ассемблере происходит сравнение?Как используется результат сравнения?Что

Краткое содержание этой серииО магииОперации в языке С (продолжение)О-нотация

Что такое «магия»?В широком смысле – это «что-то непонятное». Строгой классификации

Пример «белой магии»Функция sin. Что возвращает sin? Синус угла.А как она

Пример «черной магии»Очень сложно понять, что делает эта программа и как

Причины «магии»«Индуизм»Ручная оптимизацияМагические числаОбфускация (намеренное ухудшение читаемости кода)Недокументированные и малоизвестные особенности

«Индуизм» («индусский код»)Не индуизм:if( i > 0 && i < 100

«Магические числа»Это численные константы, смысл которых не ясен.#define SPEED_MAX 59void setSpeed(int

Как сделать черную магию белой?// Быстрый вариант функции 1/sqrt. // Быстр

Что такое интерфейс?Интерфейс – набор входов и выходов черного ящика; их

Интерфейсыdouble sin( double angleInRadians );int work( int a, int b, int

Хороший интерфейс делает черную магию белой!

Операции в языке С (продолжение)ЛогическиеБитовые

Логические операции! – логическое отрицание&& - логическое И|| - логическое ИЛИТ.к.

Логическое отрицание - !Результат выражения !A равен нулю, если А не

Логическое ИЛИ - ||Результат выражения А || B равен нулю, только

Логическое И - &&Результат выражения А && B равен единице, только

Логические операции в ассемблереИх нет! Есть только битовые.Все операции, которые называются

Битовые операции языка С~ - битовая инверсия| - битовое ИЛИ& -

Битовая инверсия - ~При битовой инверсии каждый бит двоичного представления аргумента

Битовое ИЛИ - |Результатом битового ИЛИ будет число, каждый бит которого

Битовое И - &Результатом битового И будет число, каждый бит которого

Битовое исключающее ИЛИ (XOR) - ^Если значение одного бита у аргументов

СдвигиСдвиги бывают:«просто» сдвиги – они же «логические» (без учета знака)арифметические (с

Сдвиг влево - <<

Сдвиг вправо - >>

Примеры сюрпризовint a = -1 << 1; - undefined behaviourint a

Сюрприз в сюрпризеОписания сдвигов отрицательных чисел появились в стандарте слишком поздно.Программисты

Рассмотрим два алгоритма сортировкиСортировка пузырькомСортировка выбором

Какой из них быстрее?А если взять другой массив?А если взять другой

Как узнать, какой алгоритм быстрее?Написать программу и запустить?но ее можно написать

Теоретический анализ?Какая самая долгая операция в алгоритме?Какая операция выполняется наибольшее количество

Теоретический анализ?

Теоретический анализ?

Теоретический анализ?Абстрагироваться от «железа»Абстрагироваться от входных данныхПолучается т.н. «О-нотация» (Big-Oh notation):Время

Похожие презентации

Краткое содержание предыдущей серии
Как в ассемблере происходит сравнение?
Как используется результат сравнения?
Что

Краткое содержание этой серии
О магии
Операции в языке С (продолжение)
О-нотация

Что такое «магия»?
В широком смысле – это «что-то непонятное».
Строгой классификации

Пример «белой магии»
Функция sin. Что возвращает sin?
Синус угла.
А как она

Пример «черной магии»
Очень сложно понять, что делает эта программа и как

«Индуизм» («индусский код»)
Не индуизм:
if( i > 0 && i < 100

«Магические числа»
Это численные константы, смысл которых не ясен.
#define SPEED_MAX 59
void setSpeed(int

Как сделать черную магию белой?
// Быстрый вариант функции 1/sqrt.
// Быстр

Что такое интерфейс?
Интерфейс – набор входов и выходов черного ящика; их

Интерфейсы
double sin( double angleInRadians );
int work( int a, int b, int

Операции в языке С (продолжение)
Логические
Битовые

Логические операции
! – логическое отрицание
&& - логическое И
|| - логическое ИЛИ
Т.к.

Логическое отрицание - !
Результат выражения !A равен нулю, если А не

Логическое ИЛИ - ||
Результат выражения А || B равен нулю, только

Логическое И - &&
Результат выражения А && B равен единице, только

Логические операции в ассемблере
Их нет! Есть только битовые.
Все операции, которые называются

Битовые операции языка С
~ - битовая инверсия
| - битовое ИЛИ
& -

Битовая инверсия - ~
При битовой инверсии каждый бит двоичного представления аргумента

Битовое ИЛИ - |
Результатом битового ИЛИ будет число, каждый бит которого

Битовое И - &
Результатом битового И будет число, каждый бит которого

Битовое исключающее ИЛИ (XOR) - ^
Если значение одного бита у аргументов

Сдвиги
Сдвиги бывают:
«просто» сдвиги – они же «логические» (без учета знака)
арифметические (с

Примеры сюрпризов
int a = -1 << 1; - undefined behaviour
int a

Сюрприз в сюрпризе
Описания сдвигов отрицательных чисел появились в стандарте слишком поздно.
Программисты

Рассмотрим два алгоритма сортировки
Сортировка пузырьком
Сортировка выбором

Какой из них быстрее?
А если взять другой массив?
А если взять другой

Как узнать, какой алгоритм быстрее?
Написать программу и запустить?
но ее можно написать

Теоретический анализ?
Какая самая долгая операция в алгоритме?
Какая операция выполняется наибольшее количество

Теоретический анализ?
Абстрагироваться от «железа»
Абстрагироваться от входных данных
Получается т.н. «О-нотация» (Big-Oh notation):
Время