Математика и алгоритмы

Материал из Tech_support
Перейти к: навигация, поиск

Ссылки

Морфологический анализ

Хэш-функция для целых чисел

В одно время, очень нужна была хорошая и быстрая хэш-функция для целых чисел. И случайно, в исходниках Blender`а, нашел:

int hash_func_int( int data ) {

   int key;
   
   
   key = data;
   
   key += ~(key << 16);
   key ^=  (key >>  5);
   key +=  (key <<  3);
   key ^=  (key >> 13);
   key += ~(key <<  9);
   key ^=  (key >> 17);
   
   return key;

}

Необычное использование побитового XOR в Javascript

источник

Отлаживая недавно очередной кусок чужого кода наткнулся на такой цикл:

while (--i ^ -1)  /* тело цикла */;


при этом, изначально i равно некоторому положительному числу. То есть, побитовый оператор используется здесь для целых чисел. Немного подумав, я понял, что результат побитового XOR обратится в нуль единственно в случае, когда числа равны. Тогда условие кастуется в true. В противном случае, будет не-ноль, что кастуется в false.

Получается, можно использовать побитовый XOR вместо оператора != (если мы заранее знаем, что сравниваемые величины суть числа).

Оказалось, что если использовать побитовый XOR вместо !=, появляется прирост в производительности (по крайней мере на Firefox), этот прирост стабильный (то есть он есть всегда, то больше, то меньше), но составляет всего лишь около 1%.