__builtin_clz 구현

__builtin_clz 구현

GCC(4.6+)의 구현은 무엇입니까?__builtin_clz? 인텔의 CPU 명령에 해당합니까?x86_64 (AVX)?

한마디로 이야기할 수 없군요.

CLZ(카운트 리딩 제로)와 BSR(비트 스캔 리버스)은 관련이 있지만 다릅니다.CLZ는 (비트 너비 유형에서 하나를 뺀 값) - BSR입니다. FFS(Find first set)라고도 하는 CTZ(카운트 후행 0)는 BSF(비트 스캔 포워드)와 동일합니다.

이 모든 것은 0에서 작동할 때 정의되지 않습니다!

질문에 대한 답으로 x86 및 x86_64의 대부분의 경우 __builtin_clz는 31에서 차감된 BSR 연산을 생성하고 __builting_ctz는 BSF 연산을 생성합니다.

GCC가 생성하는 어셈블리가 무엇인지 알고 싶다면, 가장 잘 알 수 있는 방법은 보는 것입니다.-S 플래그는 주어진 입력에 대해 생성된 어셈블러를 gcc 출력합니다.

gcc-S-o 테스트.테스트.c

고려 사항:

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

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

clz gcc(-O2)의 경우 x86에서 다음을 생성합니다.

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

fortz:

bsfl    %edi, %eax
ret

clz가 아닌 bsr을 원하는 경우 31 - clz를 수행해야 합니다(32비트 정수의 경우).이것은 XOR 31을 x XOR 31 == 31 - x로 설명합니다 (이 항등식은 2^y - 1 의 숫자에 대해서만 참입니다).

num = __builtin_clz(num) ^ 31;

수확량

bsrl    %edi, %eax
ret

Bit Scan Reverse(비트 스캔 역방향) 명령과 감산으로 변환해야 합니다.BSR은 선행 1의 인덱스를 제공하고, 그 다음 단어 크기에서 그것을 빼서 선행 0의 수를 얻을 수 있습니다.

편집: CPU가 LZCNT(Leading Zero Count)를 지원하는 경우 이 방법도 가능하지만 모든 x86-64 칩에 해당 명령이 있는 것은 아닙니다.

언급URL : https://stackoverflow.com/questions/9353973/implementation-of-builtin-clz