algorithm - 如何在不使用任何移位的情况下计算正位数？

在一段时间前的一次求职面试中，我被要求计算位向量结构(如无符号整数或长整数)中正数(即设置为“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等)的“强力”解决方案也不起作用。

有人知道这样的算法吗？

据我了解，它应该是一种或多或少的通用算法，不依赖于输入位向量的大小。允许所有其他按位运算和任何数学函数。

最佳答案

有一个x & (x-1) hack，如果您想了一会儿，就会清除整数中的最后一个1。休息是微不足道的。