насчёт битового поля конечноже приврал — забыл про целые числа, это подходит только для натуральных. Для целых можно попробовать хэш сочинить
В худшем случае мой подход требует n*n. а сортировка с поиском n*n*log, ИМХО