计算无符号长序列中的公共位

一个小的速度提高可能是通过先将整数或“加在一起”,然后使用结果来确定需要检查的位来实现的。您仍然需要迭代每个位,但在没有1的位上只迭代一次,而不是 values.Length

我带你去古典音乐: Bit Twiddling Hacks ,但您的目标似乎与典型的计数略有不同(即,您的“counts”变量的格式非常奇怪),但它可能会有用。

我在这里能做的最好的事情就是把它弄糊涂,然后展开内部循环。。。似乎将性能降低了一半(大约4秒,而您的8秒处理100个Ulong 100000次)。。。我使用qick命令行应用程序生成以下代码:

for (int i = 0; i < length; i++)
{
    ulong value = values[i];
    if (0ul != (value & 1ul)) counts[0]++;
    if (0ul != (value & 2ul)) counts[1]++;
    if (0ul != (value & 4ul)) counts[2]++;
    //etc...
    if (0ul != (value & 4611686018427387904ul)) counts[62]++;
    if (0ul != (value & 9223372036854775808ul)) counts[63]++;
}

那是我能做的最好的了。。。根据我的评论,在32位环境中运行它会浪费一些(我不知道有多少)。如果你担心你的表现呢 也许 让您首先将数据转换为uint。

棘手的问题。。。甚至可以让你把它封为C++,但这完全取决于你的应用程序。对不起,我帮不上忙了,也许其他人会看到我错过的东西。

耸肩 我试过了。

通过在lef中将每一位移位n*8,将64位整数中的每个字节更改为64位整数

例如

(使用该翻译的查找表)

然后,用正确的方法将所有字符相加,就得到了无符号字符和整数的数组。

必须进行8*(64位整数的数量)求和

c代码

//LOOKTABLE IS EXTERNAL and has is int64[256] ;
unsigned char* bitcounts(int64* int64array,int len)
{  
    int64* array64;
    int64 tmp;
    unsigned char* inputchararray;
    array64=(int64*)malloc(64);
    inputchararray=(unsigned char*)input64array;
    for(int i=0;i<8;i++) array64[i]=0; //set to 0

    for(int j=0;j<len;j++)
    {             
         tmp=int64array[j];
         for(int i=7;tmp;i--)
         {
             array64[i]+=LOOKUPTABLE[tmp&0xFF];
             tmp=tmp>>8;
         }
    }
    return (unsigned char*)array64;
}

这个冗余的速度比单纯的执行速度快了8倍,因为它每次可以达到8位。

我修改了代码,在较小的整数上进行更快的中断,但我仍然不确定endianess 这只适用于多达256个输入,因为它使用无符号字符来存储数据。如果您有更长的输入字符串,可以将此代码更改为最多保留2^16位计数,并将spped减少2

const unsigned int BYTESPERVALUE = 64 / 8;
unsigned int bcount[BYTESPERVALUE][256];
memset(bcount, 0, sizeof bcount);
for (int i = values.length; --i >= 0; )
  for (int j = BYTESPERVALUE ; --j >= 0; ) {
    const unsigned int jth_byte = (values[i] >> (j * 8)) & 0xff;
    bcount[j][jth_byte]++; // count byte value (0..255) instances
  }

unsigned int count[64];
memset(count, 0, sizeof count);
for (int i = BYTESPERVALUE; --i >= 0; )
  for (int j = 256; --j >= 0; ) // check each byte value instance
    for (int k = 8; --k >= 0; ) // for each bit in a given byte
      if (j & (1 << k)) // if bit was set, then add its count
        count[i * 8 + k] += bcount[i][j];

另一种可能有利可图的方法是构建一个256个元素的数组,

下面是一个4元素表的示例,它执行2位而不是8位。

int bitToSubscript[4][3] =
{
    {0},       // No Bits set
    {1,0},     // Bit 0 set
    {1,1},     // Bit 1 set
    {2,0,1}    // Bit 0 and bit 1 set.
}

然后,算法退化为:

• 将其用作小整数以索引到bitToSubscriptArray中。
• 在该数组中,提取第一个整数。这是计数数组中需要递增的元素数。
• 基于该计数,迭代行的其余部分,根据从bitToSubscript数组中提取的下标递增计数。
• 循环完成后,将原来的数字2位向右移动。。。。根据需要重复冲洗。

现在有一个问题我忽略了,在这个描述中。实际下标是相对的。您需要跟踪您在计数数组中的位置。每次循环时,都会向偏移量添加两个。向该偏移量添加bitToSubscript数组中的相对下标。

根据这个小例子,应该可以放大到您想要的大小。我认为可以使用另一个程序来生成bitToSubscript数组的源代码,这样就可以在程序中对其进行简单的硬编码。

这个方案还有其他的变化,但我希望它的平均运行速度比任何一次只运行一点的方案都要快。

猎得好。

恶毒的

我相信这会给速度带来很好的提升:

  const ulong mask = 0x1111111111111111;
  public static int[] CommonBits(params ulong[] values)
  {
    int[] counts = new int[64];

    ulong accum0 = 0, accum1 = 0, accum2 = 0, accum3 = 0;

    int i = 0;
    foreach( ulong v in values ) {
      if (i == 15) {
        for( int j = 0; j < 64; j += 4 ) {
          counts[j]   += ((int)accum0) & 15;
          counts[j+1] += ((int)accum1) & 15;
          counts[j+2] += ((int)accum2) & 15;
          counts[j+3] += ((int)accum3) & 15;
          accum0 >>= 4;
          accum1 >>= 4;
          accum2 >>= 4;
          accum3 >>= 4;
        }
        i = 0;
      }

      accum0 += (v)      & mask;
      accum1 += (v >> 1) & mask;
      accum2 += (v >> 2) & mask;
      accum3 += (v >> 3) & mask;
      i++;
    }

    for( int j = 0; j < 64; j += 4 ) {
      counts[j]   += ((int)accum0) & 15;
      counts[j+1] += ((int)accum1) & 15;
      counts[j+2] += ((int)accum2) & 15;
      counts[j+3] += ((int)accum3) & 15;
      accum0 >>= 4;
      accum1 >>= 4;
      accum2 >>= 4;
      accum3 >>= 4;
    }

    return counts;
  }

演示: http://ideone.com/eNn4O (需要更多的测试用例)

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

其中一个

unsigned int v; // count the number of bits set in 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
}

请记住,此方法的复杂性约为O(log2(n)),其中n是要计算位的数字,因此对于10个二进制文件,它只需要2个循环

你可能应该采用这种方法,用64位算术计算32位,并将其应用于每半个单词,2*15+4指令需要多少

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
   0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

http://en.wikipedia.org/wiki/SSE4