Проверка на равенство из массива чисел.

[Ароха]

Здравствуйте.
Нужен алгоритм.
Есть массив целых. Надо определить, существует ли в нем хотя-бы два не нулевых равных друг-другу числа.
Пишу для микроконтроллера, поэтому желательно обойтись математикой и бинарной логикой.
(В принципе, можно написать функцию на Си и оформить как ФБ. Но интуиция мне подсказывает, что есть арифметический способ. Только пока ничего не придумывается.)
Спасибо.

Пока у меня родилось только такое:
Обнуляем аккумулятор.
Берем очередное число из списка.
Возводим двойку в степень этого числа получаем число в бинарном представлении взведен всего один бит, сравниваем с аккумулятором, если этот-же бит взведен, то значит такое число уже было, выходим из цикла, если нет - побитово складываем с аккумулятором. Берем следующее число...
Плюсы: поиск за один проход. Возведение в степень можно заменить бинарным сдвигом.
Минусы: числа ограничены диапазоном 0-31.
Под мои нужды пока годится.

Смущает корявость решения, и что делать, если потребуются числа больше 31?

[Utkin]

Стандартно оформить отдельную подпрограмму с проходом в цикле.

Пока у меня родилось только такое:

Мутно описан алгоритм. Давайте вот для последовательности:
1
2
4
7
3
3
3
Прорешайте, как там получится по-Вашему алгоритму. И второй вариант - это пытаться оптимизировать под конкретную задачу (для микроконтроллера актуально). Для чего это надо?
Далее есть вариант, но его надо оценить по времени. Это банальная сортировка - тогда все одинаковые числа будут рядом.

[Ароха]

Алгорим такой:
1 Обнуляем аккумулятор (регистр, переменная... не важно) "А"
2 Берем очередное число из массива.
3 Возводим двойку в степень этого числа. Получаем число, в двоичном представлении которого взведен всего один бит. "К"
4 Получившееся число "К" сравниваем с аккумулятором "А" побитово.
5 Если в аккумуляторе бит, что и в нашем числе - взведен, значит мы нашли исходное равенство - выходим из функции.
6 Складываем "К" и "А" побитово.
7 если массив не пройден, идем на пункт 2
8 Прошли весь массив и ничего не нашли - совпадающих чисел нет, вываливаемся с нулем.

Получается приемлемо по скорости. Поиск за один проход, и двойка легко возводится в любую степень простым сдвигом.
Но я ограничен диапазоном 0-31. (Процессор 32-х разрядный: "Motorola MPC5200")
Пока мне этого диапазона хватает.
Просто, возможно я изобретаю очередной велосипед с квадратными колесами, вот и решил спросить.

Сортировка мне тоже пришла на ум, но на скорую руку придумалась только пузырьковая, и я её отбросил.

[Ароха]

Алгоритм не пригоден, количество возможных значений чисел в массиве увеличилось до 53х.

[Utkin]

Получившееся число "К" сравниваем с аккумулятором "А" побитово.

А чего побитно-то два числа между собой сравнить нельзя что ли?

Сортировка мне тоже пришла на ум, но на скорую руку придумалась только пузырьковая, и я её отбросил.

Ну так надо обратится к первоисточникам и найти более быстрый алгоритм. Тут нельзя угадать, там много параметров, например сколько чисел в массиве и т.д.

[min@y™]

Есть массив целых. Надо определить, существует ли в нем хотя-бы два не нулевых равных друг-другу числа.

как насчёт "взять тупо 2 указателя и погонять во вложенном цикле, сравнивая каждый с каждым до первого совпадения"?

[Poma][a]

как насчёт "взять тупо 2 указателя и погонять во вложенном цикле, сравнивая каждый с каждым до первого совпадения"?

Тут решение было за O(n). У Вас за квадрат.. Слишком резкий перепад

[min@y™]

Тут решение было за O(n). У Вас за квадрат.. Слишком резкий перепад

смотря какой размер массива.

[Poma][a]

Ну а создать не один байт, а два? При чем раздельно.. Не?