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

Битовые хаки

Ссылки

• http://algolist.manual.ru/ ,http://algolist.manual.ru/misc/morfo.php
• http://e-maxx.ru/algo/
• http://www.scriptol.com/programming/list-algorithms.php.
• http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2
• http://rain.ifmo.ru/cat/view.php/

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

• http://habrahabr.ru/post/49421/

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

В одно время, очень нужна была хорошая и быстрая хэш-функция для целых чисел. И случайно, в исходниках 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%.