Проверка четности. Простой способ

Четность числа — это свойство, которое определяет, четное или нечетное количество установленных битов (битов, равных 1) в числе. Если количество установленных битов четное, то четность равна 0 (false), если нечетное — 1 (true).

Недостатки наивного подхода:
- Количество итераций: Время выполнения пропорционально количеству установленных битов. В худшем случае (когда все биты установлены) потребуется столько итераций, сколько бит в числе.
- Эффективность: Этот метод более эффективен, чем прямой перебор всех битов, но все еще не самый быстрый из возможных.

Проверка четности с помощью таблицы поиска. Метод с побитовым сдвигом

Использование таблицы поиска для проверки четности позволяет существенно ускорить процесс, так как четность для каждого байта вычисляется заранее и хранится в таблице. Это позволяет избежать многократного выполнения битовых операций.

Метод с побитовым сдвигом заключается в уменьшении количества битов до одного байта, для которого затем можно использовать таблицу поиска. Он уменьшает 32-битное число до одного байта с помощью побитовых операций XOR.

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

Проверка четности с помощью таблицы поиска. Метод с указателем

Использование таблицы поиска для проверки четности позволяет существенно ускорить процесс, так как четность для каждого байта вычисляется заранее и хранится в таблице. Это позволяет избежать многократного выполнения битовых операций.

Метод с указателем заключается в использовании указателя на байты числа и вычисление четности для XOR всех четырех байтов.

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

Проверка четности 32-битного числа с использованием умножения

Метод вычисления четности числа с использованием умножения позволяет эффективно вычислять четность 32-битных чисел с помощью всего восьми операций.

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.

Прикладная задача на структуры данных из продакшена Яндекс Еды.

Дано: ~500k ресторанов и ~3M зон доставки в виде многоугольников. Нужно по координате пользователя за ~50 мс найти все рестораны, которые реально могут привезти заказ, причём зоны постоянно меняются.

В статье ребята разбирают, почему для геоиндекса не подошли Geohash и H3, и как в итоге пришли к R-дереву с логарифмическим поиском и отдельными индексами для ресторанов, ритейла и самовывоза. Есть схемы вставки, поиска и оценка сложности.

👉 Ссылка на разбор

Проверка четности 64-битного числа с использованием умножения

Метод вычисления четности числа с использованием умножения позволяет эффективно вычислять четность 64-битных чисел с помощью всего восьми операций.

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.

Вычисление деления по модулю для степени двойки без оператора деления

Вычисление остатка от деления числа на степень двойки можно выполнить без использования оператора деления. Это делается с помощью побитового И (&) с маской, представляющей степень двойки минус один.

Пример использования:
Если n = 29 и s = 3, то делитель d = 8:
- В двоичной системе n=11101
- Маска d−1=7 или 0111
- m = 11101 & 0111 = 0101 (5 в десятичной системе)
Таким образом, 29 % 8 = 5.

Вычисление деления по модулю для числа вида (1 << s) - 1 без оператора деления

Для деления по модулю числа на значение, равное одной меньше степени двойки (например, 1, 3, 7, 15 и т.д.), можно использовать метод, который не требует оператора деления. Вместо этого используется серия побитовых операций и циклов.

Пример использования:
Если n = 29 и s = 3:
- Делитель d = 7.
- В цикле вычисляются промежуточные значения m, пока n не станет меньше или равно d.
- Результат m = 29 % 7 = 1.

👨‍💻Задачи точного покрытия — фундамент для многих алгоритмических подходов. Но пока теория лежит на полке, она мало что меняет в вашем инженерном мышлении

На открытом уроке мы разберем Dancing Links через практику: соберем пентамино на столе, представим фигуры в виде строк матрицы и разберемся, как работает поиск с возвратом. Когда алгоритм становится наглядным, вы начинаете понимать, что на самом деле происходит внутри.

Если вы хотите развивать алгоритмическое мышление, системно улучшать свои решения и уверенно чувствовать себя в задачах уровня middle+, такие разборы — обязательная часть роста.

📆 Встречаемся 22 декабря в 20:00 МСК в преддверие старта курса «Алгоритмы и структуры данных», регистрация открыта: https://otus.pw/eq4Y/?erid=2VtzqvhDroC

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Подсчет количества замыкающих нулевых битов справа с использованием деления по модулю и таблицы поиска

Этот метод позволяет быстро найти количество замыкающих нулевых битов в 32-битном числе, используя деление по модулю и таблицу поиска. Метод основан на уникальном соответствии значений остатка от деления на 37 позициям битов.

Преимущества метода
- Эффективность: Метод требует всего 4 операции, что делает его быстрым.
- Компактность: Использование небольшой таблицы позволяет значительно ускорить вычисления по сравнению с линейным методом.

Недостатки метода
- Ограниченность: Метод предназначен для 32-битных чисел и требует адаптации для чисел другой разрядности.

Произведения всех элементов массива, кроме текущего

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет массив, где i-ый элемент является произведением всех элементов nums, кроме nums[i] (каждое произведение гарантированно умещается в 32-битное целое число).

Для решения задачи без использования операции деления и за O(n) времени, можно использовать метод предварительного вычисления произведений. Идея заключается в том, чтобы использовать два прохода по массиву: один для вычисления произведений слева от текущего элемента и другой для вычисления произведений справа от текущего элемента.

Пример:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]