Thực hiện __builtin_clz

Question

Việc thực hiện GCC (4.6+) __builtin_clz là gì? Liệu nó có tương ứng với một số lệnh CPU trên Intel x86_64 (AVX)?

Answer 1

Cần dịch thành hướng dẫn Bit Scan Reverse và trừ. BSR cho chỉ số của hàng đầu 1, và sau đó bạn có thể trừ từ kích thước từ để có được số lượng các số 0 đứng đầu.

Chỉnh sửa: nếu CPU của bạn hỗ trợ LZCNT (Đếm đầu số không), thì điều đó có thể sẽ thực hiện thủ thuật, nhưng không phải tất cả chip x86-64 đều có lệnh đó.

Answer 2

Có, nó tương ứng với lệnh CPU BSR (bit scan reverse).

Dưới đây là một mẫu mã có thể giúp bạn:

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

Vâng, và không.

CLZ (đếm số 0 đứng đầu) và BSR (đảo ngược bit quét) có liên quan nhưng khác nhau. CLZ bằng (loại bit chiều rộng ít hơn một) - BSR. CTZ (đếm dấu 0), cũng biết là FFS (tìm tập đầu tiên) giống như BSF (quét bit về phía trước.)

Lưu ý rằng tất cả những điều này không xác định khi hoạt động trên không!

Trong câu trả lời cho câu hỏi của bạn, phần lớn thời gian trên x86 và x86_64, __builtin_clz tạo phép toán BSR trừ từ 31 (hoặc bất kỳ chiều rộng kiểu của bạn), và __builting_ctz tạo ra một hoạt động BSF.

Nếu bạn muốn biết người lắp ráp GCC đang tạo ra gì, cách tốt nhất để biết là xem. Lá cờ -S sẽ có đầu ra gcc lắp ráp nó tạo ra cho các đầu vào cho trước:

gcc -o -S test.S test.c

xem xét:

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

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

On x86 cho clz gcc (-O2) tạo ra:

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

và cho ctz:

bsfl %edi, %eax 
ret 

Lưu ý rằng nếu bạn thực sự muốn bsr, chứ không phải clz, bạn cần phải làm 31 - clz (đối với số nguyên 32 bit.) Điều này giải thích XOR 31, như x XOR 31 == 31 - x (điều này sắc là chỉ đúng đối với số lượng từ 2^y - 1) vì vậy:

num = __builtin_clz(num)^31; 

mang

bsrl %edi, %eax 
ret