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.