Экстремальная оптимизация целочисленного двоичного поиска

Я пишу программу, которая должна будет выполнять очень большое количество бинарных поисков - не менее 10 ^{15 - в тесном цикле. Они вместе с небольшим количеством побитовых операций составят более 75% времени выполнения программы, поэтому важно сделать их быстрыми. (Как реализовано сейчас, это занимает более 95% времени, но при этом используется совсем другая реализация [не поиск], которую я заменяю.)}

Массив для поиска (конечно, это не нужно быть реализован в виде массива) очень мало. В моем текущем случае он состоит из 41 64-битного целого, хотя были бы полезны методы оптимизации массивов других размеров. (Ранее я сталкивался с подобными проблемами.)

Я могу заранее профилировать данные, чтобы определить, какие диапазоны наиболее вероятны и как часто происходит совпадение. Собрать эту информацию не так-то просто, но я должен получить ее к концу дня.

Мой код будет на C, возможно, с использованием встроенной сборки; он будет скомпилирован с последней версией gcc. Ответы на любом языке приветствуются; если вы предпочитаете (например) Фортран, я могу перевести.

Итак: Как я могу эффективно реализовать этот поиск?

Пояснение: Я на самом деле использую поиск, чтобы проверить членство, а не использовать местоположение в массиве. Решение, которое отбрасывает эту информацию, является приемлемым.

Окончательный код:

long ispow3_tiny(ulong n)
{
    static ulong pow3table[] = {
#ifdef LONG_IS_64BIT
        12157665459056928801, 0, 4052555153018976267, 1350851717672992089, 0, 450283905890997363, 150094635296999121, 0, 50031545098999707, 0, 16677181699666569, 5559060566555523, 0, 1853020188851841, 617673396283947, 0, 205891132094649, 0, 68630377364883, 22876792454961, 0, 7625597484987, 2541865828329, 0, 847288609443, 282429536481, 0, 94143178827, 0, 31381059609, 10460353203, 0,
#endif
        3486784401, 1162261467, 0, 387420489, 0, 129140163, 43046721, 0, 14348907, 4782969, 0, 1594323, 531441, 0, 177147, 0, 59049, 19683, 0, 6561, 2187, 0, 729, 0, 243, 81, 0, 27, 9, 0, 3, 1
    };

    return n == pow3table[__builtin_clzl(n)];
}