Объясни XOR-трюк и ограничения битов в JS
Вопрос
Объясни, как найти единственный непарный элемент через XOR, почему это работает и какие особенности побитовых операций в JS нужно помнить.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Свойства x ^ x = 0 и x ^ 0 = x
Коммутативность: порядок элементов не важен
O(n) времени и O(1) памяти против O(n) у Map
В JS операнды приводятся к 32-битным целым со знаком
Для больших чисел BigInt, для беззнакового вида >>> 0
Что могут спросить следом
- Как найти два непарных числа?
- Как найти число, которое встречается один раз, если остальные по три?
- Как получить двоичную запись отрицательного числа?
Разбор
XOR одинаковых чисел равен нулю, XOR с нулём не меняет число, а порядок операций не важен. Поэтому если пройти по массиву и накопить XOR всех элементов, каждая пара сократится, и останется непарное число. Это один проход, O(n) времени и O(1) памяти, тогда как Map частот тратит O(n) памяти. В JS важно помнить, что все побитовые операторы работают с 32-битными целыми со знаком: числа больше 2³¹ - 1 переполняются, дробная часть отбрасывается. Для больших значений использую BigInt, а чтобы увидеть биты отрицательного числа, пишу (x >>> 0).toString(2). Для двух непарных чисел беру общий XOR, выделяю любой единичный бит через x & -x и делю числа на две группы по этому биту.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.