查找字符的位总和

Question

我需要一个大小约为 8 个布尔值的队列。每次推动都应该从尾部摧毁一个项目。这可以通过在资源有限的应用程序中 char 来实现。

不过我只关心那些“旗帜”的总和，而不关心它们各自的状态。我怎样才能找到一个8位char的集合位的总和？

Answer 1

我想出了两个办法

一个方法是用一个变量来统计和，每次push的时候都维护这个变量，变量的变化取决于你push什么，pop什么。

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

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

它将return x 的二进制表示的最后一个 1 int。

这样就可以得到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 v;
}

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

   return v;
}

查找字符的位总和

Find sum of bits of a char

c++

algorithm

binary