Реализация __builtin_clz

Ответ 1

Он должен перевести на команду Bit Scan Reverse и вычесть. BSR дает индекс ведущего 1, а затем вы можете вычесть это из размера слова, чтобы получить число начальных нулей.

Редактирование: если ваш процессор поддерживает LZCNT (Leading Zero Count), то это, вероятно, тоже сделает трюк, но не все чипы x86-64 имеют эту инструкцию.

Ответ 2

Да и нет.

CLZ (начальный ноль отсчета) и BSR (бит-сканирование назад) связаны друг с другом, но разные. CLZ равно (тип бит ширина меньше один) - BSR. CTZ (отсчет конечного нуля), также известный как FFS (найти первый набор), совпадает с BSF (бит-сканирование вперед.)

Обратите внимание, что все они undefined при работе на ноль!

В ответ на ваш вопрос, большую часть времени на x86 и x86_64, __builtin_clz генерирует операцию BSR, вычитаемую из 31 (или независимо от вашей ширины вашего типа), а __builting_ctz генерирует операцию BSF.

Если вы хотите знать, что генерирует ассемблер GCC, лучше всего это посмотреть. Флаг -S будет иметь gcc вывод ассемблера, сгенерированного для данного входа:

gcc -S -o test.S test.c

Рассмотрим:

unsigned int clz(unsigned int num) {
    return __builtin_clz(num);
}

unsigned int ctz(unsigned int num) {
    return __builtin_ctz(num);
}

В x86 для clz gcc (-O2) генерируется:

bsrl    %edi, %eax
xorl    $31, %eax
ret

и для ctz:

bsfl    %edi, %eax
ret

Обратите внимание, что если вы действительно хотите bsr, а не clz, вам нужно сделать 31 - clz (для 32-битных целых чисел). Это объясняет XOR 31, так как x XOR 31 == 31 - x (это идентификация только истинно для чисел из 2 ^ y - 1) So:

num = __builtin_clz(num) ^ 31;

дает

bsrl    %edi, %eax
ret

Ответ 3

Да, это соответствует команде CPU BSR (бит сканирования назад).

Вот пример кода, который может вам помочь:

int a=20; //10100

//trailing zeroes
cout<<__builtin_ctz(a)<<endl;   //gives 2
cout<<__builtin_ctz(a<<4)<<endl;    //gives 6

//leading zeroes
cout<<__builtin_clz(a)<<endl;   //gives 27
cout<<__builtin_clz(a>>4)<<endl;    //gives 31

cout<<__builtin_clz(0)<<endl;   //gives 32