Efective способ избежать целочисленного переполнения при умножении?
Я работаю над хеш-функцией, которая получает строку, как введено.
Прямо сейчас я делаю цикл, и в хеше (международная переменная) умножается на значение, и затем код ASCII для текущего символа добавляется к соединению.
hash = hash * seed + string[i]
Но иногда, если строка является достаточно большой, там существует целочисленное переполнение, что я могу сделать для предотвращения его при поддержании той же структуры хеша? Возможно, немного операции, включенной в цикле?
4 ответа
Почему бы не использовать long для хранения результата? Затем вы можете применить методы такие как этот для обнаружения переполнения
Если у вас есть доступ к большему типу данных, вы можете сделать что-то вроде этого:
int32_t hash, seed;
int64_t temporary;
temporary = hash * seed + string[i];
hash = ( temporary >> 32 ) ^ ( temporary & 0xFFFFFFFF );
В противном случае вам придется вручную размножить хэш и seed на два значения, добавить string[i] с переполнением, а затем ^ эти два значения.
Хеши неявно несут потери, поэтому можно просто оставить биты переполнения, если только нет конкретной причины, по которой они нужны, например, для соответствия существующему алгоритму.
Существует несколько возможных интерпретаций вашего вопроса, и, как отмечено в комментариях, вам может потребоваться пояснение.
Однако единственная разумная интерпретация состоит в том, что вы хотите ограничить значение хеш-функции определенным диапазоном. Предполагая, что тогда, если бы диапазон был от 0 до HASH_TABLE_SIZE - 1, тогда:
hash = (hash * seed + string[i]) % HASH_TABLE_SIZE ;
или если размер таблицы является степенью двойки, используйте маску:
#define HASH_TABLE_SIZE (0x01<<8) // 2^8 (256) table
#define HASH_MODULO_MASK (HASH_TABLE_SIZE - 1)
...
hash = (hash * seed + string[i]) & HASH_MODULO_MASK ;
Хеш-функции, подобные этой, должны переполняться. Вы должны объявить "хэш" без знака. Если вам действительно нужен int, просто используйте hash & 0x7fffffff. Просмотрите алгоритм Фаулера-Нолля-Во , вы найдете там ссылки на исходный код.