[HN Gopher] Iterating over Bit Sets Quickly
       ___________________________________________________________________
        
       Iterating over Bit Sets Quickly
        
       Author : liamswayne
       Score  : 32 points
       Date   : 2024-02-24 17:11 UTC (5 hours ago)
        
 (HTM) web link (alexharri.com)
 (TXT) w3m dump (alexharri.com)
        
       | kccqzy wrote:
       | 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.
        
         | pizlonator wrote:
         | Totally. The hamming weight thing this post does is available
         | as an instruction on most cpus.
        
         | corysama wrote:
         | 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
        
         | anonymoushn wrote:
         | 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.
        
       | bawolff wrote:
       | I was recently reading about Roaring https://roaringbitmap.org/
       | which is a highly optimized compressed bitset implementation. I
       | reccomend reading about it if you are interested in this sort of
       | thing. The talk at https://roaringbitmap.org/talks/ is especially
       | good.
        
       | halfcat wrote:
       | Ah, brings back memories of chess programming where this stuff
       | was discussed often. See [1] for more of this. I always found
       | Kogge Stone [2] pretty cool, a kind of bit-twiddling flood-fill.
       | 
       | [1] https://www.chessprogramming.org/Bit-Twiddling
       | 
       | [2] https://www.chessprogramming.org/Kogge-Stone_Algorithm
        
       | vanderZwan wrote:
       | That was an enjoyable read, and all of these bit twiddling tricks
       | are great. Having said that I'm fairly sure that using Math.clz32
       | is faster for finding the bit index than using the Hamming
       | weight. That also lets you iterate from the most-to-least
       | significant bit if you want.
       | 
       | Can't blame the author for not trying that though, it's probably
       | one of the most obscure and rarely used library functions in
       | JavaScript.
       | 
       | (I will bookmark this article for the next time I need to iterate
       | over bitmaps LSB first though)
       | 
       | [0] https://developer.mozilla.org/en-
       | US/docs/Web/JavaScript/Refe...
        
       | Robin_Message wrote:
       | I don't understand how all that bit twiddling is faster in the
       | 100% case (where the branch predictor should be hitting home
       | runs.)
       | 
       | I guess it means a js branch is very expensive even when
       | predictable but that feels slightly unsatisfactory.
        
       ___________________________________________________________________
       (page generated 2024-02-24 23:00 UTC)