Could a lookup table be faster even for fairly sparse bits? I'm imagining something like uint8_t *result; uint8_t numpositions[]; uint64_t positions0[];

Could a lookup table be faster even for fairly sparse bits? I'm imagining something like uint8_t *result; uint8_t numpositions[]; uint64_t positions0[]; uint64_t positions1[]; ... *(uint64_t*) result = positions0[byte0] result += numpositions[byte0] *(uint64_t*) result = positions1[byte1] result += numpositions[byte1] ... Or probably accumulating results in a register until you get 8.