Где применяется
1. Задача
Дальше в курсе понадобятся два низкоуровневых инструмента: работа с отдельными битами числа и немного теории чисел. Бит это одна двоичная цифра, 0 или 1.
У пользователя есть права: чтение, запись, удаление, администрирование и ещё десяток. Самый очевидный способ их хранить: по одному значению true/false на каждое право, в маленьком объекте или массиве. Это работает. Но теперь у каждого пользователя целый набор true/false, и проверка «может ли он писать?» каждый раз лезет в этот набор.
Можно хранить плотнее. Целое число записано в памяти как ряд из 32 битов, и каждый бит уже сам по себе переключатель «да/нет». Упакуй все права в одно число. Тогда в базе это одно поле, передаёшь ты одно значение, а любой переключатель меняется одной операцией.
Для этого нужно уметь читать и менять один бит, не задевая остальные.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитfindUnique([5, 3, 5, 6, 3])| 8 | 4 | 2 | 1 | |
|---|---|---|---|---|
| acc | 0 | 0 | 0 | 0 |
Каждое число встречается дважды, кроме одного. acc начинается с 0, а a XOR b переключает биты a там, где у b стоит 1.
Столбики: 32 бита числа, старший слева, высокий столбик означает 1. Проверка каждого бита их только читает; приём Кернигана сбрасывает каждую посчитанную единицу, поэтому его столбики в конце обнулены.
Одна операция: один шаг цикла: проверка одного бита или сброс одного бита. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n)O(k)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- найти единственное или уникальное число через XOR
- установить, снять, переключить или проверить бит
- упаковать много флагов да/нет в одно целое число
- подсчёт установленных битов или проверка степени двойки
Похоже, но не то
- Хеш-множество / словарь (Hash set / map)
Множество отвечает про принадлежность для любого ключа. Битовая маска умеет это для 32 известных элементов без памяти.
- Математика и теория чисел (НОД, решето, модульная арифметика) (Math and number theory (GCD, sieve, modular))
Оба работают с самим числом. Та страница про делители и простые, эта про биты.
- Бэктрекинг (Backtracking)
Подмножества можно перечислить простым счётом от нуля. Бэктрекинг строит тот же список рекурсией.
- Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Поразрядная сортировка читает разряды, иногда как биты. Её цель группировка, а не переключение.
Одна операция стоит O(1) на 32-битном значении. Проход по битам это O(32), то есть константа.
На LeetCode
Задачи, где читают, ставят или считают отдельные биты числа, например число единичных битов, сравнение двух чисел бит за битом или разворот битов. Маска 1 << i с AND, OR и NOT работает с одним битом за раз.
Это countBits из урока. Прибавляй x & 1 и сдвигай вправо, пока x не станет 0.
Сделай XOR двух чисел, тогда разные биты станут единицами, и посчитай их через countBits.
Читай бит i через getBit и ставь бит 31 минус i в ответе. В конце сделай >>> 0, ведь битовые операции в JavaScript дают знаковые 32-битные числа.
Проверь каждую позицию бита через getBit. Где у c стоит 0, переверни каждую единицу в a и b, а где 1, переверни один бит, только если оба равны 0.
bits[i] равно bits[i >> 1] + (i & 1), так что каждый счёт берёт уже готовый.