Существует классическая задача для собеседований, часто формулируемая следующим образом:
Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только одно из чисел не имеет пары. Необходимо предложить алгоритм, который за минимальное число проходов по массиву определяет число, не имеющее пары.
Полагаю, никто не обидится, если я тут же приведу и решение задачи: уникальный элемент будет совпадать с 
-суммой всех элементов массива, вычисляемой за линейное время.
Предлагаю поразмыслить над другой вариацией данной задачи. Что, если все элементы, кроме искомого, будут присутствовать в массиве не парами, а тройками? Насколько при этом усложнится решение и останется ли оно линейным?
Попробуем решать по аналогии. 
подошёл из-за того, что обладает двумя замечательными свойствами (помимо ассоциативности и коммутативности, естественно):
Символ 
в данной записи — это математическое обозначение операции 
. Предположим на минуту, что существует операция 
, удовлетворяющая похожим свойствам:
В этом случае 
-сумма всех элементов массива дала бы правильный ответ. Поэтому займёмся построением такой функции.
Все мы привыкли воспринимать 
как "побитовое исключающее или" (тут даже название выбрано подходящее — eXclusive OR), но я предлагаю взглянуть на эту операцию под немного другим углом — как на "поразрядное сложение по модулю 2". Не зря ведь символ 
так похож на плюс.
Вроде бы поменяли только название, а мысли появляются уже совсем другие. Битовое представление целых чисел — это просто представление в двоичной позиционной системе счисления. И если каждый бит воспринимать как число 0 или 1, то их 
— это в точности сложение по модулю два.
Следуя подобным рассуждениям, в качестве 
можно взять поразрядное сложение по модулю 3 в троичной системе счисления. Оно будет удовлетворять всем нужным свойствам, осталось только написать реализацию.
Открою тайну названия статьи. Существует достаточно распространённый способ кодирования чисел — двоично-десятичный формат. Суть его в том, что каждые 4 бита данных хранят один десятичный разряд числа, что существенно облегчает перевод в строковое представление и обратно.
По аналогии хранение каждого троичного разряда по отдельности в двух битах данных можно назвать двоично-троичным кодированием числа. Например:
Понятное дело, для хранения обычного беззнакового 32-битного целого числа потребуется больший объём данных. А именно, 
бит информации, что легко войдёт в 64-битный формат типа long.
Реализация конвертирования из двоичного в двоично-троичный формат довольно топорная — обычный цикл с чтением/записью нужных бит по смещению:
static long to3(int n) {
long ln = ((long) n) & 0xFFFFFFFFL;
long result = 0L;
for (int offset = 0; ln != 0L; ln /= 3, offset += 2) {
result |= (ln % 3) << offset;
}
return result;
}static int from3(long n) {
long result = 0L;
for (int offset = 40; offset >= 0; offset -= 2) {
result = (result * 3) + ((n >> offset) & 0x3L);
}
return (int) result;
}Что же касается операции 
, то для неё тоже доступна простая реализация:
static long xor3(long a, long b) {
long result = 0L;
for (int offset = 0; offset < 42; offset += 2) {
long digit = ((a >> offset) & 0x3L) + ((b >> offset) & 0x3L);
result |= (digit % 3) << offset;
}
return result;
}Её уже можно тестировать (и она даже работает!), но я ей не доволен.
Понимаете, "битовые" функции обычно выглядят так (это метод из класса Long):
public static long reverse(long i) {
i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
i = (i << 48) | ((i & 0xffff0000L) << 16) |
((i >>> 16) & 0xffff0000L) | (i >>> 48);
return i;
}Меня такой код восхищает, потому что он наверняка супер оптимален и с первого взгляда совершенно непонятно, как работает. От подобных алгоритмов я получаю особое удовольствие.
Именно поэтому я перепишу реализацию xor3, избавившись от циклов и условий:
static long xor3(long a, long b) {
long o = a & b & 0xAAAAAAAAAAAAAAAAL;
long c = (a + b) - (o << 1);
long m = c & (c >>> 1) & 0x5555555555555555L;
return (c & ~(m | m << 1)) | (o >>> 1);
}Далее последуют объяснения, что вообще происходит и как люди до такого доходят.
Итак, стоит задача одновременной обработки 21-й пары бит (можно и больше), руководствуясь следующими правилами:
$$display$$begin{array}{|} hline oplus_3&00&01&10\ hline 00&00&01&10\ hline 01&01&10&00\ hline 10&10&00&01\ hline end{array}$$display$$
Пара бит "11" просто не может попасться, поскольку она соответствовала бы разряду со значением 3, которое в троичной системе счисления не встречается.
Что будет, если просто сложить аргументы a и b? Данная операция сохранит "локальность" пар бит почти для всех вариантов входных данных. Единственное исключение — сумма 10 и 10, которая при переполнении залезет на территорию соседней пары.
К данной проблеме может быть два подхода — предотвращение или исправление последствий. Второй вариант оказывается гораздо более простым. Из получившейся суммы нужно просто вычесть все биты переполнения. Находятся они только там, где старшие биты каждой пары равны единице. Отсюда рождается первая магическая переменная:
long o = a & b & 0xAAAAAAAAAAAAAAAAL;Константа, на первый взгляд непонятная, в двоичном представлении выглядит предельно просто: 0b101010...10. В ней единицы стоят через одну, пропуская самый младший бит. Это помогает отрезать от a & b всё то, что нас сейчас не интересует. Сдвинув o на 1 бит влево, мы как раз получим все биты переполнения, появляющиеся при сложении
long c = (a + b) - (o << 1);Переменная c хранит значение, очень близкое к результату, но с ошибками:
- В ней есть пары бит
11, которые по модулю 3 должны быть заменены на00. - Все результаты сложения
10и10равны00, а должны быть01.
Исправим эти ошибки по порядку. Найти пары бит, равные 11, не сложно, мы уже делали что-то очень похожее.
long m = c & (c >>> 1) & 0x5555555555555555L;Магическая константа здесь — это не что иное, как ~0xAAAAAAAAAAAAAAAAL, то есть число, в котором единичные биты стоят через один, начиная с самого младшего. Тем самым в значении m единичные биты будут стоять младшими битами пар, соответствующих парам 11 в значении c.
Выражение m | m << 1 представляет эти пары целиком. Избавиться от них теперь можно двумя способами. Какой выбирать — дело вкуса:
c -= m | m << 1;c &= ~(m | m << 1);
Разобраться с последней ошибкой проще простого: нужно добавить биты там, где мы складывали 10 и 10. А равны они в точности o >>> 1. Поэтому итоговый код выглядит именно так:
return (c & ~(m | m << 1)) | (o >>> 1);Но это ещё не всё. Избавившись от циклов и условий в одной из функций, я совсем позабыл о циклах и условиях в двух оставшихся — to3 и from3. Можно ли их оптимизировать подобным образом?
Смотря как посмотреть. Если хочется по-честному переводить в троичную систему счисления, то придётся делить/умножать на 3, тут никуда не деться. НО ведь можно заменить саму операцию на более оптимальную: сопоставлять 32-х разрядному двоичному числу другое 32-х разрядное троичное число так, чтобы разным двоичным числам соответствовали разные троичные (такие отображения называются инъективными), при этом значения двоичного и троичного чисел совпадать не обязаны.
Например, прямое отображение двоичных разрядов в троичные (
). Однако здесь реализация будет всё такой же неудобной. Самый простой вариант, который приходит мне на ум — это поместить чётные биты int в одну половину значения типа long, а нечётные — в другую. Код станет элементарным:
static long to3(int n) {
long ln = ((long) n) & 0xFFFFFFFFL;
return (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32;
}
static int from3(long n) {
return (int) (n | n >>> 32);
}Такие методы и заинлайнить можно, а значит решение исходной задачи будет выглядеть следующим образом:
static int find(int[] v) {
long res = 0L;
for (int n : v) {
long ln = ((long) n) & 0xFFFFFFFFL;
res = xor3(res, (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32);
}
return (int) (res | res >>> 32);
}Как видите, не очень сложно. Я бы даже сказал, что код выглядит красивым (хотя и нуждается в пояснениях). Надеюсь, что вы разделяете моё мнение.
Спасибо за внимание!
Автор: Иван Бессонов
