Die Dokumentation zumparallele Einzahlungsanweisung (PDEP) in Intels Bit Manipulation Instruction Set 2 (BMI2) beschreibt die folgende serielle Implementierung für den Befehl (C-ähnlicher Pseudocode):

U64 _pdep_u64(U64 val, U64 mask) {
  U64 res = 0;
  for (U64 bb = 1; mask; bb += bb) {
    if (val & bb)
      res |= mask & -mask;
    mask &= mask - 1;
  }
  return res;
}

Siehe auch Intelspdep insn ref manuelle Eingabe.

Dieser Algorithmus ist O (n), wobei n die Anzahl der gesetzten Bits in @ ismask, was offensichtlich den schlimmsten Fall von O (k) hat, wobei k die Gesamtzahl der Bits in @ imask.

Ist ein effizienterer Worst-Case-Algorithmus möglich?

Ist es möglich, eine schnellere Version zu erstellen, die davon ausgeht, dassval hat höchstens ein Bit gesetzt, dh entweder gleich 0 oder gleich1<<r für einen Wert vonr von 0 bis 63?