Identification of the bit position of a selected instance of a particular bit value in a binary bit string

A circuit for identifying one or more bit positions of instances of a selected bit value in an N-bit input bit string including P input substrings, the circuit comprising:

• a plurality of adders that compute, in parallel, sums of bits in each of the P input substrings;
• a plurality of zero position detectors that, for each of the P input substrings for which a corresponding sum differs from a threshold sum, detecting one or more bit positions of the selected bit value;
• correction logic that generates adjustment indications indicative of a number of detected instances of the selected bit value;
• and
• a plurality of output substring adjusters that, based on the detected bit positions and the adjustment indications, collectively output one or more output vectors identifying a bit position of at least an Mth instance of the selected bit value in the input bit string.

A design structure tangibly embodied in a machine-readable storage device for designing, manufacturing, or testing an integrated circuit, the design structure comprising:

• a circuit for identifying one or more bit positions of instances of a selected bit value in an N-bit input bit string including P input substrings, the circuit comprising:
• a plurality of adders that compute, in parallel, sums of bits in each of the P input substrings;
• a plurality of zero position detectors that, for each of the P input substrings for which a corresponding sum differs from a threshold sum, detecting one or more bit positions of the selected bit value;
• correction logic that generates adjustment indications indicative of a number of detected instances of the selected bit value;
• and
• a plurality of output substring adjusters that, based on the detected bit positions and the adjustment indications, collectively output one or more output vectors identifying a bit position of at least an Mth instance of the selected bit value in the input bit string.