查找 char 的位总和[已关闭]

Question

我需要一个大小约为 8 个布尔值的队列。每次推动都会从尾部摧毁一个物品。这可以通过资源有限的应用程序中的

char

来实现。

但是我只关心这些“标志”的总和，而不关心它们的个体状态。如何求 8 位

char

的设置位之和？

Answer 1

我想出了两种方法。

一种方法是使用一个变量来计算总和，每当你压入时，你都会维护该变量，变量的变化取决于你压入的内容和弹出的内容。

另一种方法是一种称为“lowbit”的算法

int lowbit(int x) {
    return x & -x;
}

它将返回 x 的二进制表示的最后 1 个整数。

这样就可以得到x的二进制表示中'1'的个数。

例如，这样的代码。

int sum_of_1(int x) {
    int res = 0;
    while (x != 0) res++, x -= lowbit(x);
    return res;
}

Answer 2

计算位设置，Brian Kernighan 的方式

// count the number of bits set in v
unsigned char sum( unsigned char v )
{
   unsigned int c; // c accumulates the total bits set in v
   for (c = 0; v; c++)
   {
      v &= v - 1; // clear the least significant bit set
   }

   return c; // c has the count, v is zero
}

unsigned char push( unsigned char v, bool in )
{
   v << 1;
   if( in )
   {
      v |= 1;
   }

   return v;
}