35

What is the implementation of GCC's (4.6+) __builtin_clz? Does it correspond to some CPU instruction on Intel x86_64 (AVX)?

1

2 Answers 2

37

Yes, and no.

CLZ (count leading zero) and BSR (bit-scan reverse) are related but different. CLZ equals (type bit width less one) - BSR. CTZ (count trailing zero), also know as FFS (find first set) is the same as BSF (bit-scan forward.)

Note that all of these are undefined when operating on zero!

In answer to your question, most of the time on x86 and x86_64, __builtin_clz generates BSR operation subtracted from 31 (or whatever your type width is), and __builting_ctz generates a BSF operation.

If you want to know what assembler GCC is generating, the best way to know is to see. The -S flag will have gcc output the assembler it generated for the given input:

gcc -S -o test.S test.c

Consider:

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

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

On x86 for clz gcc (-O2) generates:

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

and for ctz:

bsfl    %edi, %eax
ret

Note that if you really want bsr, and not clz, you need to do 31 - clz (for 32-bit integers.) This explains the XOR 31, as x XOR 31 == 31 - x (this identity is only true for numbers of the from 2^y - 1) So:

num = __builtin_clz(num) ^ 31;

yields

bsrl    %edi, %eax
ret
2
  • does this mean std::countl_zero() needs to test for zero? Commented Nov 27, 2022 at 10:26
  • It should be noted that GCC has ffs builtins, with: ffs(x) = 1 + ctz(x), therefore ffs indexes bits from 1: while __builtin_ctz(0) is undefined. __builtin_ffs(0) is perfectly valid (and returns 0),
    – Bruno
    Commented Jan 1 at 6:57
27

It should translate to a Bit Scan Reverse instruction and a subtract. The BSR gives the index of the leading 1, and then you can subtract that from the word size to get the number of leading zeros.

Edit: if your CPU supports LZCNT (Leading Zero Count), then that will probably do the trick too, but not all x86-64 chips have that instruction.

6
  • It seems the link is broken.
    – martian
    Commented May 23, 2018 at 3:38
  • Link should be fixed now. Commented Jul 7, 2018 at 5:18
  • 1
    If you compiler with -mbmi1, you're telling gcc that lzcnt is available on all CPUs that will run this binary. (or much better -march=haswell or -march=bdver2 or -march=znver1 or whatever, to tune for a specific CPU as well as enabling instruction sets.) Commented Jul 7, 2018 at 5:34
  • Why does gcc provide __builtin_clz but not bit scan reverse?
    – user3310334
    Commented Mar 28, 2021 at 13:17
  • godbolt.org/z/5re8vWzq8 yep, depending on instruction set both are being generated
    – sehe
    Commented Oct 2, 2021 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.