, _ /| | | _/_\_ >_< .-\-/. | / | | \_ | \ \| |\__(/ /(`---') | / / \ | _.' \'-' / | `----'`=-=' ' 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