Решение задачи о поиске двух недублирующихся элементов в потоке

Всем привет. Нашел, наконец-то, красивое решение задачи о поиске 2-ух недублирующихся элементов в большом входном потоке целых чисел (см. концовку моего предыдущего поста). Своим умом, к сожалению, до этого решения не дошел, но так как решение очень красивое, и мне оно понравилось, привожу его ниже (кстати, еще раз убедился во вменяемости практически абсолютного большинства участников форума rsdn.ru :).

Итак, напомню условие задачи. Есть большой входной поток целых чисел, про который известно, что в нем все числа дублируются кроме двух. Найти эти 2 числа за константное количество проходов с использованием константного количества памяти.


Решение. Обозначим как A и B те два неповторяющихся числа. За первый проход xor-им все числа потока.  В результате имеем X = A ^ B (все парные элементы не оказывают на результат никакого влияния).  В этом числе X обязательно должен быть единичный бит, так как известно, что числа A и B различны, а значит хоть в одном бите, но отличаются друг от друга. Находим этот единичный бит. Допустим, он в позиции P числа X. Затем за второй проход считаем 2 XOR-суммы:
1. Тех чисел, для которых бит P установлен в 1.
2. Тех чисел, для которых бит P установлен в 0 (или просто всех чисел, которые не попали в предыдущее множество).

В результате мы получаем для новых числа: X1 и X2. И это те самые числа, которые не дублируются! Откуда это следует ? Понятно, что числа A и B попадут в разные группы (1 или 2), так как в одном из них бит P будет установлен в 1, а в другом - в 0. То есть, в каждой группе у нас будет ровно по одному неповторяющемуся числу. С другой стороны все остальные элементы каждой группы будут разнесены так, что если число N попало в группу 1, то и его дубликат тоже попадет в эту же группу, так как бит P у обоих чисел будет либо установлен в 1, либо нет. Таким образом, наша задача сводится к нахождению единственно недублирующегося числа во входном потоке, то есть, к предыдущей задаче. А её мы решать уже умеем: достаточно получить XOR-сумму всех элементов потока, и эта сумма и будет равна искомому числу. Вот так просто и очень красиво )


Какие могут быть оптимизационные решения ? Ну, во-первых, можно считать XOR-сумму только для варианта, когда бит P установлен (или не установлен). Тогда второе число
B = X XOR X1. Для решения задачи в один проход (только вдумайтесь! :) мы могли бы заранее создать константное количество накопительных регистров по числу анализируемых битов, в которых при первом же проходе формировать XOR-суммы чисел, для которых текущий бит установлен, а затем уже в конце использовать имеющиеся результаты.

В общем, что хочется сказать в завершение. Еще раз убеждаемся, какую важную роль играет алгоритмическая оптимизация в общем оптимизационном процессе решения задачи.