Как рассчитать количество положительных битов без использования каких-либо сдвигов?

Во время собеседования, которое я проводил некоторое время назад, меня попросили вычислить количество положительных (т.е. установленных в "1") битов в структуре битового вектора (например, целое число без знака или длинное). Мое решение было довольно простым в C #:

int CountBits(uint input)
{
   int reply = 0;
   uint dirac = 1; 
   while(input != 0)
   {
      if ((input & dirac) > 0) reply++;
      input &= ~dirac;
      dirac<<=1;
   }
   return reply;
}

Затем меня попросили решить задачу без использования без использования каких-либо сдвигов: ни явных (например, «<<» или «>>»), ни неявных (например, умножение на 2). Решение «грубой силы» с использованием потенциальной строки из 2 (например, 0, 1, 2, 4, 8, 16 и т. Д.) Тоже не подойдет.

Кто-нибудь знает такой алгоритм?

Насколько я понял, это должен быть своего рода более или менее общий алгоритм, который не зависит от размера входного битового вектора. Разрешены все остальные побитовые операции и любые математические функции.