,    _
                  /|   | |
                _/_\_  >_<
               .-\-/.   |
              /  | | \_ |
              \ \| |\__(/
              /(`---')  |
             / /     \  |
          _.'  \'-'  /  |
          `----'`=-='   '    hjw
          C Thaumaturgy Center
       
       You like magic?
       
       
       Count bits set (rank) from the most-significant bit upto a given
       position
       
       The following finds the the rank of a bit, meaning it returns the sum
       of bits that are set to 1 from the most-signficant bit downto the bit
       at the given position.
       
       uint64_t v; // Compute the rank (bits set) in v from the MSB to pos.
       unsigned int pos; // Bit position to count bits upto.
       uint64_t r; // Resulting rank of bit at pos goes here.
       // Shift out bits after given position.
       r = v>> (sizeof(v) * CHAR_BIT - pos);
       // Count set bits in parallel.
       // r = (r & 0x5555...) + ((r>> 1) & 0x5555...);
       r = r - ((r>> 1) & ~0UL/3);
       // r = (r & 0x3333...) + ((r>> 2) & 0x3333...);
       r = (r & ~0UL/5) + ((r>> 2) & ~0UL/5);
       // r = (r & 0x0f0f...) + ((r>> 4) & 0x0f0f...);
       r = (r + (r>> 4)) & ~0UL/17;
       // r = r % 255;
       r = (r * (~0UL/255))>> ((sizeof(v) - 1) * CHAR_BIT);
       
       Juha Järvi sent this to me on November 21, 2009 as an inverse
       operation to the computing the bit position with the given rank, which
       follows.
       
       
 (TXT) Get the full database.
 (HTM) Got some C magic? Send the spell source to 20h@r-36.net
 (DIR) << back to bitreich.org