3

I have found out about __builtin_ctzll to count trailing zeros of a 64bit int really fast through the post Intrinsic to count trailing zero bits in 64-bit integers?.

I'm a beginner to C++ and don't know how to include this function.

I tried to use #include, but that didn't make any sense. I found out that this "builtin" comes from GNU, but I didn't know what to do with that information. How can I prepare the right library/extension for my project?

Brian61354270
  • 8,690
  • 4
  • 21
  • 43
Paul
  • 41
  • 5

3 Answers3

9

For unsigned types, you can use the standard/portable C++20 function std::countr_zero.

It'll return the same thing as GCC's __builtin_ctzll, but note:

If the value is 0 when using __builtin_ctzll, the result is undefined, while std::countr_zero(0ull) will return the number of bits in the integer.

In VS2022, you'll find the language setting in the menu Project\Properties\Configuration Properties\General C++ Language Standard. It's set to C++14 by default. Change that to C++20 (or Preview if you'd like to try out some C++23 features too).

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • Thanks for this clear review, I changed the version and now it works. However std::countr_zero (20 sec for 1 billion) is about 10-times slower than BitScanReverse (2 sec for 1 billion) on my System. (I have used 1024 returning 10 as input) – Paul Jul 17 '23 at 18:49
  • @Paul You're welcome. Performance measurements can be tricky. I find it highly unlikely that MS would put such an inferior function in their standard library if there's one available that does it 10 times faster in their own API. – Ted Lyngmo Jul 17 '23 at 19:01
  • 1
    You should be right actually. I probably did something wrong. – Paul Jul 18 '23 at 13:59
  • @Paul I can't say for sure, but that's my idea when I can't see how you did it. – Ted Lyngmo Jul 19 '23 at 00:30
2

If you're using MSVC, you can use its _BitScanReverse64 builtin (or "compiler intrinsic" as it likes to call them) to replicate the behavior of GCC's __builtin_ctzll. This function provides the index of the first non-zero bit position, which is equivalent to the number of trailing zeros.

So,

int pos = __builtin_ctzll(x);

can be replaced by

unsigned long pos;
unsigned char is_nonzero = _BitScanReverse64(&pos, x);

This intrinsic is also arguably nicer than __builtin_ctzll since it forces a check for whether the argument is zero. GCC's __builtin_ctzll puts the burden to include a check for that case on the user, and leaves behavior for a zero argument undefined.

Note that the similarly named __lzcnt family of intrinsics in MSVC counts leading zeros (like GCC's clz family), not trailing zeros. For whatever reason, MSVC doesn't provide a like-named family of __tzcnt intrinsics.

Brian61354270
  • 8,690
  • 4
  • 21
  • 43
  • @MooingDuck That counts leading zeros, not trailing zeros, no? – Brian61354270 Jul 17 '23 at 15:31
  • I should have read the problem and function names better. My mistake – Mooing Duck Jul 17 '23 at 15:32
  • 1
    Thanks, that works very well and is pretty efficient. std::countr_zero however doesn't work, the program says std doesn't have such a function. – Paul Jul 17 '23 at 17:23
  • 1
    @Paul Could you confirm what version of what compiler are you using? `std::countr_zero` is only available if you set your standard version to C++20 or later. Your compiler may have support for C++20, but is defaulting to an older standard version. If you are using MSVC, you may be able to enable C++20 support with `/std:c++20` or `/std:c++latest`. – Brian61354270 Jul 17 '23 at 17:25
  • 1
    @Paul `std::countr_zero` works just fine in Visual Studio if you use C++20 instead of the default, which is C++14. I've updated my answer to show how you make the change. – Ted Lyngmo Jul 17 '23 at 18:04
1

As the name suggests, "builtin" functions are literally built into the compiler that provides them. They're just special identifiers that the compiler provides special behavior for. You do need to load any additional libraries or include any header files to use them. The compiler will natively recognize them and provide their special, compiler-specific behavior.

The only way to use a particular builtin function is to use the compiler that provides it. For example, the function __builtin_ctzl is provided as a builtin in GCC. If you use GCC as your compiler, you will be able to use it without any additional steps. If you use a different compiler, you'll need to look into a different solution, such as a similar builtin that your compiler provides or a similar library function.

Brian61354270
  • 8,690
  • 4
  • 21
  • 43