News for hackers. Stuff that matters.
Re:Iterating over Bit Sets Quickly by kccqzy on Saturday February 24, 2024 @02:51PM (#39494619)
I am of the opinion that tasks like finding the least significant set bit should be inside the standard library of all languages, so that compilers (including JIT ones) can use the efficient CPU instruction to calculate it, like bsr/bsf on x86 ones. This is the first time I've heard of the `word & -word` trick because in C/C++ I'd just use __builtin_ctzll and __builtin_clzll.

Oh and same for saturating arithmetic.

Re:Iterating over Bit Sets Quickly by corysama on Saturday February 24, 2024 @03:34PM (#39494931)
Same. I’m very happy about the addition of https://en.cppreference.com/w/cpp/numeric/countr_zero There’s a proposal to get them to work with std::bitset. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p31... Don’t know if it got anywhere.

Meanwhile, you might appreciate the venerable https://graphics.stanford.edu/~seander/bithacks.html

Re:Iterating over Bit Sets Quickly by pizlonator on Saturday February 24, 2024 @03:23PM (#39494850)
Totally. The hamming weight thing this post does is available as an instruction on most cpus.
Re:Iterating over Bit Sets Quickly by emmelaich on Saturday February 24, 2024 @10:06PM (#39497223)
Exposed as popcount() in recent versions of Python and C++.
Re:Iterating over Bit Sets Quickly by anonymoushn on Saturday February 24, 2024 @05:24PM (#39495671)
You end up using some of these tricks even if you can access ctz, because it's faster to mask off the lowest bit in a way that doesn't depend on the output of the ctz instruction.
Re:Iterating over Bit Sets Quickly by jandrewrogers on Saturday February 24, 2024 @06:06PM (#39495966)
At least on x86 processors, most idiomatic bit manipulation expressions like `word & -word` or `word & (word - 1)` compile to a single fast ALU instruction. __builtin_clz and similar are comparatively more expensive on many architectures.
Re:Iterating over Bit Sets Quickly by ndesaulniers on Saturday February 24, 2024 @08:40PM (#39496823)
GCC now implements __builtin_ctzg for things like C23 _BitInt (and more). Makes implementing C23 stdbit.h more straightforward.