Здравствуйте, мыщъх, Вы писали:

М>Здравствуйте, Mystic, Вы писали:

M>>Здравствуйте, мыщъх, Вы писали:

M>>Как такой вопрос: быстрая реализация BSF для uint64_t на C, без ассемблера?
М>встречный вопрос -- а накуя? вы можете назвать хоть один компилятор где нет таких расширений? в ms, gcc, intel'е они есть и libc есть.

(1) Для разминки мозгов
(2) Вопрос скорее в платформах. Есть спарки, есть ARM-ы. Какой там синтаксис соответствующей ассемблерной команды я сказать не могу, да и проверить не могу. Но могу прописать в configure, что если у нас на x86 и не x86_64, то включить общий вариант функции. А там энтузазисты поправят.

М>быстрая реализация на си? гм... без профайлера не скажу. табличная реализация vs калькуляция. трудно сказать, что будет быстрее на современных процессорах, тем более без указания типа процессора.

Одними и самых быстрых считается эти, по сути 4-5 ассемблерных команд без всяких условий.

int trailingZeroCount(U64 bb) {
   static const int lookup67[67+1] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33, -1 };
   return lookup67[(bb & -bb) % 67];
}

const int index64[64] = {
   63,  0, 58,  1, 59, 47, 53,  2,
   60, 39, 48, 27, 54, 33, 42,  3,
   61, 51, 37, 40, 49, 18, 28, 20,
   55, 30, 34, 11, 43, 14, 22,  4,
   62, 57, 46, 52, 38, 26, 32, 41,
   50, 36, 17, 19, 29, 10, 13, 21,
   56, 45, 25, 31, 35, 16,  9, 12,
   44, 24, 15,  8, 23,  7,  6,  5
};
 
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x07EDD5E59A4E28C2);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

Некоторые другие быстрые алгоритмы можно найти тут.