__builtin_clz的實現

Question

GCC的實現（4.6+）__builtin_clz？它是否與英特爾x86_64 (AVX)上的某些CPU指令相對應？

Answer 1

它應該翻譯成Bit Scan Reverse指令和減法。 BSR給出前導1的索引，然後你可以從字大小中減去前導零的數量。編輯：如果你的CPU支持LZCNT（Leading Zero Count），那麼這也可能會實現，但並不是所有的x86-64芯片都有這個指令。

Answer 2

是的，它對應於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 

Answer 3

yes和no。

CLZ（count leading zero）和BSR（bit-scan reverse）是相關但不同的。 CLZ等於（輸入比特寬度小於1） - BSR。 CTZ（計數結尾零），也稱爲FFS（找到第一組）與BSF（位向前掃描）相同。

請注意，所有這些在零操作時都是不確定的！

在回答你的問題時，大部分時間在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); 
} 

在86爲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）因此：

num = __builtin_clz(num)^31; 

產生

bsrl %edi, %eax 
ret