如何在不使用任何班次的情况下计算正位数？

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)黑客,如果你暂时考虑一下,最后1用整数清除.休息是微不足道的.