Где применяется
1. Задача
На складе каждую посылку сканируют дважды: на входе и на выходе. За день в журнале сканов каждый ID встречается ровно два раза. Исключение одно: посылка потерялась, и её ID записан всего раз. Нужно найти этот ID среди миллиона сканов.
Надёжный способ: завести карту счётчиков, посчитать, сколько раз встретился каждый ID, и найти тот, у которого счётчик равен 1. Это работает, но требует O(n) памяти: миллион счётчиков ради одного числа.
Пара свойств операций над битами даёт тот же ответ одной строкой и с O(1) памяти. Об этих свойствах и пойдёт речь.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- найти единственное или уникальное число через XOR
- установить, снять, переключить или проверить бит
- упаковать много флагов да/нет в одно целое число
- подсчёт установленных битов или проверка степени двойки
Похоже, но не то
- Хеш-множество / словарь (Hash set / map)
Множество отвечает про принадлежность для любого ключа. Битовая маска умеет это для 32 известных элементов без памяти.
- Математика и теория чисел (НОД, решето, модульная арифметика) (Math and number theory (GCD, sieve, modular))
Оба работают с самим числом. Та страница про делители и простые, эта про биты.
- Бэктрекинг (Backtracking)
Подмножества можно перечислить простым счётом от нуля. Бэктрекинг строит тот же список рекурсией.
- Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Поразрядная сортировка читает разряды, иногда как биты. Её цель группировка, а не переключение.
Одна операция стоит O(1) на 32-битном значении. Проход по битам это O(32), то есть константа.
На LeetCode
Задачи, где одно число пропало или осталось без пары, и быстрые проверки младшего бита. XOR сокращает равные числа, x & (x-1) гасит младший единичный бит, а x & -x оставляет только его.
Это findUnique из урока. Сделай XOR всего, и каждая пара сократится в 0.
У степени двойки ровно один единичный бит, так что n больше 0 и n & (n-1) равно 0.
Сделай XOR всех индексов от 0 до n и всех чисел, и останется пропавшее число.
Сделай XOR всего, получишь a XOR b, возьми его младший бит через x & -x и раздели числа на две группы по этому биту.
Посчитай каждый из 32 битов по всем числам, и биты, чей счёт не делится на 3, принадлежат одиночному числу.