pattern heroPT–23LeetCode Extension

Битовые операции

Число — это ряд нулей и единиц, и операции над битами меняют их все разом. Поэтому многие задачи решаются без лишней памяти: например, XOR сам вычёркивает одинаковые числа.

Вариант
P11 Битовые операцииXOR · 1×

Пример задачи: в [4, 7, 2, 4, 1, 7, 6, 1, 6] каждое число встречается дважды, кроме одного. Найти его.

041722344157667186421вес разрядаnum—x000= 0
ещё не дошли; бит 0текущее число; бит, который только что переключилсяуже в x; бит 1 в xбит 1 в num: он переключает xпара, которая сократиласьчисло без пары

x начинается с 0 = 000: x xor 0 возвращает x

x = 0 = 000num = –
01/21
сначала · назад · пуск · шаг
Скорость
1function singleNumber(nums):
2 x = 0
3 for each num in nums:
4 x = x xor num
5 return x

← → шаг · пробел — пауза

Как узнать

числа парами и одно лишнее, подсчёт или разворот битов, степени двойки, сложение двоичных строк или «O(1) памяти» на целых числах.

Как решать такие задачи

  1. Выпиши несколько маленьких входов в двоичном виде и посмотри на каждый столбец битов отдельно.
  2. Выбери операцию: xor сокращает пары, & проверяет или сбрасывает биты, | ставит их, << и >> сдвигают.
  3. Держи ответ в одном целом числе и обновляй его по ходу, вместо множества или списка.
  4. Проверь крайние случаи: 0, одно число, старший бит и отрицательные числа в твоём языке.

Вариант: По битам

То же, но разбираем число по одному биту: смотрим на младший бит и сдвигаем число, чтобы на его место пришёл следующий. Подходит, когда нужно что-то сделать с каждым битом, например посчитать единицы.

  1. Читай младший бит через n & 1 и переходи к следующему через n >> 1.
  2. Сделай нужное с каждым битом: посчитай, перенеси в ответ, сравни с битом другого числа.
  3. n & (n - 1) сбрасывает младшую единицу: крути цикл по нему, чтобы пройти только по единицам, или проверяй степень двойки через n & (n - 1) == 0.
  4. Если все числа встречаются по три раза, кроме одного, посчитай единицы в каждой из 32 позиций: позиции, где счёт не делится на 3, — это биты ответа.

Где встречается

  • Права на файлы в Unix. Чтение, запись и запуск — это три бита, поэтому chmod 755 — три тройки битов. Чтобы проверить право, система берёт его бит маской.
  • RAID 5. Вместе с данными RAID 5 хранит их XOR. Если один диск сломался, XOR уцелевших дисков восстанавливает его: всё, кроме потерянного, сокращается.
  • Поисковые движки. Lucene и Apache Spark хранят множества номеров документов как битовые карты (Roaring Bitmaps). Пересечь два множества — значит сделать побитовое И, по 64 номера за одну операцию.