Документация дляинструкция параллельного депозита (PDEP) в наборе команд Intel для управления битами 2 (BMI2) описывает следующую последовательную реализацию для инструкции (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;
}

Смотрите также Intelpdep insn ref ручной ввод.

Этот алгоритм O (n), где n это количество установленных битов вmaskкоторый, очевидно, имеет наихудший случай O (k), где k - общее количество битов вmask.

Возможен ли более эффективный алгоритм наихудшего случая?

Можно ли сделать более быструю версию, предполагающую, чтоval имеет не более одного установленного бита, т.е. либо равно 0, либо равно1<<r для некоторого значенияr от 0 до 63?