La documentación para elinstrucción de depósito paralelo (PDEP) en el Conjunto de instrucciones de manipulación de bits de Intel 2 (BMI2) describe la siguiente implementación en serie para la instrucción (pseudocódigo 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;
}

Ver también Intel'spdep entrada manual ref..

Este algoritmo es O (n), donde n es el número de bits establecidos enmask, que obviamente tiene un peor caso de O (k) donde k es el número total de bits enmask.

¿Es posible un algoritmo de peor caso más eficiente?

¿Es posible hacer una versión más rápida que asuma queval tiene como máximo un conjunto de bits, es decir, es igual a 0 o igual1<<r por algún valor der de 0 a 63?