Биномиальная куча
Cтруктура данных, используемая для реализации очередей с приоритетами. Биномиальные кучи состоят из набора биномиальных деревьев, каждое из которых соответствует определенному структурному свойству.
Ключевые характеристики:
Биномиальное дерево порядка k — это древовидная структура, состоящая из 2^k узлов, которая формируется путем рекурсивного объединения меньших биномиальных деревьев.
Каждое биномиальное дерево соответствует свойству порядка кучи, где значение каждого узла больше или равно значениям его дочерних элементов.
Преимущество:
Операция слияния биномиальных куч очень эффективна, поскольку использует преимущества упорядоченной структуры биномиальных деревьев.
Cтруктура данных, используемая для реализации очередей с приоритетами. Биномиальные кучи состоят из набора биномиальных деревьев, каждое из которых соответствует определенному структурному свойству.
Ключевые характеристики:
Биномиальное дерево порядка k — это древовидная структура, состоящая из 2^k узлов, которая формируется путем рекурсивного объединения меньших биномиальных деревьев.
Каждое биномиальное дерево соответствует свойству порядка кучи, где значение каждого узла больше или равно значениям его дочерних элементов.
Преимущество:
Операция слияния биномиальных куч очень эффективна, поскольку использует преимущества упорядоченной структуры биномиальных деревьев.
Левосторонняя куча
Тип древовидной структуры данных. Ключевой особенностью левого дерева является то, что оно удовлетворяет левому свойству
Левое свойство:
⁃ Значение каждого узла больше или равно значениям в его левом и правом поддеревьях.
⁃ Ранг (длина нулевого пути) любого правого потомка меньше или равен рангу его левого брата.
Преимущества:
Эффективная операция слияния делает левые деревья подходящими для приложений, где объединение очередей с приоритетами является обычной операцией.
Случаи использования:
Левые деревья находят применение в сценариях, где требуются очереди с динамическим приоритетом и эффективным слиянием. Примеры включают алгоритмы сетевой маршрутизации и некоторые проблемы оптимизации.
Тип древовидной структуры данных. Ключевой особенностью левого дерева является то, что оно удовлетворяет левому свойству
Левое свойство:
⁃ Значение каждого узла больше или равно значениям в его левом и правом поддеревьях.
⁃ Ранг (длина нулевого пути) любого правого потомка меньше или равен рангу его левого брата.
Преимущества:
Эффективная операция слияния делает левые деревья подходящими для приложений, где объединение очередей с приоритетами является обычной операцией.
Случаи использования:
Левые деревья находят применение в сценариях, где требуются очереди с динамическим приоритетом и эффективным слиянием. Примеры включают алгоритмы сетевой маршрутизации и некоторые проблемы оптимизации.
Двоичное дерево
Cтруктура данных, состоящая из узлов, где каждый узел имеет не более двух дочерних элементов, называемых левым дочерним элементом и правым дочерним элементом.
Основные характеристики:
⁃ Каждый узел в двоичном дереве имеет не более двух дочерних элементов: левого и правого дочерних элементов.
⁃ Узлы без дочерних узлов называются листьями, а узлы, имеющие хотя бы одного дочернего узла, — внутренними узлами.
⁃ Самый верхний узел двоичного дерева называется корнем, а узлы без родителя являются корнями своих поддеревьев.
Операции:
⁃ Вставка: добавление нового узла в дерево с сохранением свойств двоичного дерева.
⁃ Удаление: удаление узла из дерева с сохранением его структуры.
⁃ Поиск: поиск определенного узла в дереве.
Cтруктура данных, состоящая из узлов, где каждый узел имеет не более двух дочерних элементов, называемых левым дочерним элементом и правым дочерним элементом.
Основные характеристики:
⁃ Каждый узел в двоичном дереве имеет не более двух дочерних элементов: левого и правого дочерних элементов.
⁃ Узлы без дочерних узлов называются листьями, а узлы, имеющие хотя бы одного дочернего узла, — внутренними узлами.
⁃ Самый верхний узел двоичного дерева называется корнем, а узлы без родителя являются корнями своих поддеревьев.
Операции:
⁃ Вставка: добавление нового узла в дерево с сохранением свойств двоичного дерева.
⁃ Удаление: удаление узла из дерева с сохранением его структуры.
⁃ Поиск: поиск определенного узла в дереве.
Linux для чайника:
• Разбор утилит
• Разъяснения на простых примерах о том, как:
- Поднять HTTP сервер
- Отлаживать свои Bash-скрипты
- Логировать выполнение команд
• Различная вспомогательная информация
• Разбор утилит
• Разъяснения на простых примерах о том, как:
- Поднять HTTP сервер
- Отлаживать свои Bash-скрипты
- Логировать выполнение команд
• Различная вспомогательная информация
Побитовая операция исключающее ИЛИ (XOR)
Побитовая операция - это способ манипулировать отдельными битами в двоичном представлении чисел.
Отдельно рассмотрим операцию исключающего ИЛИ, которая обозначается символом
Побитовая операция - это способ манипулировать отдельными битами в двоичном представлении чисел.
Отдельно рассмотрим операцию исключающего ИЛИ, которая обозначается символом
^. Возвращает 1 для бита только если один из соответствующих битов в операндах равен 1, а другой 0, иначе возвращает 0.Сдвиг вправо (Right Shift)
Сдвиг вправо - это побитовая операция, которая перемещает все биты числа вправо на определенное количество позиций.
Сдвиг вправо обозначается символом
Сдвиг вправо - это побитовая операция, которая перемещает все биты числа вправо на определенное количество позиций.
Сдвиг вправо обозначается символом
>>. При таком сдвиге все биты числа перемещаются вправо на указанное количество позиций. При этом для положительных чисел свободные позиции слева заполняются нулями, а для отрицательных - единицами.Вычислить XOR от 1 до n
XOR (исключающее ИЛИ) — это бинарная операция, которая возвращает истину (1), если число битов равных 1 входных данных нечётное, и ложь (0) в противном случае.
Теперь, рассмотрим XOR от
Но что происходит, если n не делится на 4?
Если
Если
Если
XOR (исключающее ИЛИ) — это бинарная операция, которая возвращает истину (1), если число битов равных 1 входных данных нечётное, и ложь (0) в противном случае.
Теперь, рассмотрим XOR от
1 до n. Можно заметить, что если n делится на 4, то XOR всех чисел от 1 до n будет равен n. Это происходит потому, что для каждого числа, кроме n, существует парное число (то есть число, которое делится на 4, и смежное с ним число), и XOR пар чисел равен 0. Таким образом, если n делится на 4, результат XOR от 1 до n будет равен n.Но что происходит, если n не делится на 4?
Если
n % 4 == 1, то XOR от 1 до n равен 1.Если
n % 4 == 2, то XOR от 1 до n равен n + 1.Если
n % 4 == 3, то XOR от 1 до n равен 0.Set bits. Простой метод
Для подсчета количества единиц в двоичном представлении целого числа, можно использовать простейший метод, который заключается в переборе всех битов целого числа. Далее проверить, установлен ли бит, и если да, то увеличить переменную, отвечающую за установленное количество битов.
Для подсчета количества единиц в двоичном представлении целого числа, можно использовать простейший метод, который заключается в переборе всех битов целого числа. Далее проверить, установлен ли бит, и если да, то увеличить переменную, отвечающую за установленное количество битов.
Set bits. Алгоритм Брайана Кернигана
Для подсчета количества единиц в двоичном представлении целого числа, можно использовать алгоритм Брайана Кернигана.
Смысл алгоритма заключается в том, что вычитание единицы из десятичного числа переворачивает все биты после крайнего правого установленного бита (который равен 1), включая самый правый установленный бит.
Для подсчета количества единиц в двоичном представлении целого числа, можно использовать алгоритм Брайана Кернигана.
Смысл алгоритма заключается в том, что вычитание единицы из десятичного числа переворачивает все биты после крайнего правого установленного бита (который равен 1), включая самый правый установленный бит.
Сложение двоичных чисел, представленных в виде строк
Для сложения строк рассмотрим алгоритм сложения "столбиком":
1) Инициализация. Создаем пустую строку для результата (res) и переменную для переноса (carry).
2) Сложение с конца. Проходим по обоим строкам с конца к началу, складывая соответствующие биты и перенос.
3) Формирование результата. Добавляем текущий бит результата в начало строки res, обновляем перенос.
4) Перенос. Если после обработки всех битов остался перенос, добавляем его к результату.
5) Возврат. Возвращаем итоговую строку результата.
Для сложения строк рассмотрим алгоритм сложения "столбиком":
1) Инициализация. Создаем пустую строку для результата (res) и переменную для переноса (carry).
2) Сложение с конца. Проходим по обоим строкам с конца к началу, складывая соответствующие биты и перенос.
3) Формирование результата. Добавляем текущий бит результата в начало строки res, обновляем перенос.
4) Перенос. Если после обработки всех битов остался перенос, добавляем его к результату.
5) Возврат. Возвращаем итоговую строку результата.
Умножение двух чисел с помощью побитовых операций
Одним из интересных методов является алгоритм Русского крестьянина.
Идея состоит в том, чтобы удвоить первое число и многократно разделить второе число пополам, пока второе число не станет равным 1. В процессе, когда второе число становится нечетным, к результату добавляется первое число.
Одним из интересных методов является алгоритм Русского крестьянина.
Идея состоит в том, чтобы удвоить первое число и многократно разделить второе число пополам, пока второе число не станет равным 1. В процессе, когда второе число становится нечетным, к результату добавляется первое число.
Определить, имеют ли два целых числа противоположные знаки
Чтобы определить, имеют ли два целых числа противоположные знаки, можно использовать побитовые операции или операторы сравнения.
При использовании операции побитового исключающего ИЛИ (XOR), если два числа 𝑥 и 𝑦 имеют противоположные знаки, то их побитовое XOR выражение 𝑥⊕𝑦 будет иметь старший бит равным 1. Это объясняется тем, что старший бит в числе определяет его знак: 0 для положительных чисел и 1 для отрицательных чисел.
Этот метод более эффективный, чем второй. Во втором методе используются два оператора сравнения, однако, побитовая операция XOR более эффективна по сравнению с операцией сравнения.
Чтобы определить, имеют ли два целых числа противоположные знаки, можно использовать побитовые операции или операторы сравнения.
При использовании операции побитового исключающего ИЛИ (XOR), если два числа 𝑥 и 𝑦 имеют противоположные знаки, то их побитовое XOR выражение 𝑥⊕𝑦 будет иметь старший бит равным 1. Это объясняется тем, что старший бит в числе определяет его знак: 0 для положительных чисел и 1 для отрицательных чисел.
Этот метод более эффективный, чем второй. Во втором методе используются два оператора сравнения, однако, побитовая операция XOR более эффективна по сравнению с операцией сравнения.
Проверить, равны ли два числа, не используя арифметические операторы и операторы сравнения.
Для проверки равенства двух чисел можно использовать побитовую операцию NOT (~) и побитовую операцию AND (&).
Алгоритм:
- Проверка (a & ~b) == 0 убедится, что все биты, установленные в a, также установлены в b.
- Проверка (b & ~a) == 0 убедится, что все биты, установленные в b, также установлены в a.
- Если обе проверки равны нулю, значит, оба числа имеют одинаковые биты, то есть они равны.
Для проверки равенства двух чисел можно использовать побитовую операцию NOT (~) и побитовую операцию AND (&).
Алгоритм:
- Проверка (a & ~b) == 0 убедится, что все биты, установленные в a, также установлены в b.
- Проверка (b & ~a) == 0 убедится, что все биты, установленные в b, также установлены в a.
- Если обе проверки равны нулю, значит, оба числа имеют одинаковые биты, то есть они равны.
Вычисление абсолютного значения без ветвлений
Абсолютное значение числа — это неотрицательное значение этого числа без учета его знака.
Ветвления - это условные операции, такие как if, else или тернарный оператор '? :'.
Вместо использования ветвлений, можно использовать битовые операции, так как они могут снижать производительность из-за предсказаний ветвлений и возможных ошибок в этих предсказаниях. Особенно это критично в высокопроизводительных системах или на процессорах, где ветвления могут быть дорогими.
Абсолютное значение числа — это неотрицательное значение этого числа без учета его знака.
Ветвления - это условные операции, такие как if, else или тернарный оператор '? :'.
Вместо использования ветвлений, можно использовать битовые операции, так как они могут снижать производительность из-за предсказаний ветвлений и возможных ошибок в этих предсказаниях. Особенно это критично в высокопроизводительных системах или на процессорах, где ветвления могут быть дорогими.
Найти минимум или максимум между двумя числами без ветвлений
Иногда требуется найти минимум или максимум двух целых чисел, избегая использования ветвлений. Это может быть полезно на редких архитектурах, где ветвления являются очень дорогими операциями и отсутствуют инструкции условного перемещения.
Как это работает:
1. Побитовые операции: (x ^ y) вычисляет побитовое XOR между x и y.
2. Преобразование условия в маску: -(x < y) преобразует логическое выражение (x < y) в побитовую маску: все единицы, если условие истинно, и все нули, если условие ложно.
3. Комбинирование с y: ((x ^ y) & -(x < y)) сохраняет значение x, если x меньше y, и обнуляет его в противном случае.
4. Финальный XOR: y ^ (...) окончательно комбинирует результат с y.
Если x < y, то маска будет состоять из всех единиц, и результат будет равен x. В противном случае, результат останется равен y.
В большинстве современных процессоров использование условных операторов и тернарных операторов будет оптимальным, так как компиляторы могут эффективно обрабатывать такие конструкции. Однако понимание того, как можно избежать ветвлений с помощью побитовых операций, расширяет ваше знание оптимизаций и может быть полезно в специфических случаях.
Иногда требуется найти минимум или максимум двух целых чисел, избегая использования ветвлений. Это может быть полезно на редких архитектурах, где ветвления являются очень дорогими операциями и отсутствуют инструкции условного перемещения.
Как это работает:
1. Побитовые операции: (x ^ y) вычисляет побитовое XOR между x и y.
2. Преобразование условия в маску: -(x < y) преобразует логическое выражение (x < y) в побитовую маску: все единицы, если условие истинно, и все нули, если условие ложно.
3. Комбинирование с y: ((x ^ y) & -(x < y)) сохраняет значение x, если x меньше y, и обнуляет его в противном случае.
4. Финальный XOR: y ^ (...) окончательно комбинирует результат с y.
Если x < y, то маска будет состоять из всех единиц, и результат будет равен x. В противном случае, результат останется равен y.
В большинстве современных процессоров использование условных операторов и тернарных операторов будет оптимальным, так как компиляторы могут эффективно обрабатывать такие конструкции. Однако понимание того, как можно избежать ветвлений с помощью побитовых операций, расширяет ваше знание оптимизаций и может быть полезно в специфических случаях.