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

Question

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

有人知道这样的算法吗？

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

Answer 1

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