Мотивация: хочу использовать bsearch
(двоичный поиск) для быстрого поиска в отсортированном списке 121-битных неотрицательных целых чисел (все они имеют ровно 121 бит, хотя могут иметь начальные нули). Эти целые числа слишком велики, чтобы хранить их отдельно int
с, и так далее, так что я планирую сделать их mpz_t
(с помощью GMP).
Просматривая руководство, GMP не имеет bsearch
эквивалент (хотя, поправьте меня, если я ошибаюсь), что приводит меня к:
Вопрос: Можем ли мы использовать
memcmp
или что-то похожее, чтобы сравнить два неотрицательных целых числа с равным количеством битов, хранящихся какmpz_t
? Если так, то каков правильный синтаксис?
Если это возможно, поиск должен быть достаточно эффективным.
Я также открыт для альтернативных предложений относительно (а) структур данных для хранения этих 121-разрядных целых чисел, допускающих быстрый поиск в C ++, (б) методов поиска по целым числам, которые не используют memcmp
,
Если они только 121-битные целые, почему бы не использовать собственные 128-битные расширения int: http://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html ? Это должно быть намного быстрее, поскольку вы можете избежать любых «дорогостоящих» операций, таких как memcpy, все ваши сравнения должны быть одной инструкцией.
Других решений пока нет …