A documentação para oinstrução de depósito paralelo (PDEP) no Conjunto de instruções de manipulação de bits da Intel 2 (BMI2) descreve a seguinte implementação serial para a instrução (pseudocódigo do tipo C):

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;
}

Veja também Intelpdep entrada manual da ref do insn.

Este algoritmo é O (n), onde n é o número de bits definidos emmask, que obviamente tem o pior caso de O (k), em que k é o número total de bits emmask.

É possível um algoritmo de pior caso mais eficiente?

É possível criar uma versão mais rápida que assuma queval tem no máximo um conjunto de bits, ou seja, igual a 0 ou igual a1<<r por algum valor der de 0 a 63?