计算无​​符号长整数中的常见位

Question

我正在寻找比以下更快的算法。给定一个64位无符号整数序列，返回序列中设置的每个64位的次数。

例子：

4608 = 0000000000000000000000000000000000000000000000000001001000000000 
4097 = 0000000000000000000000000000000000000000000000000001000000000001 
2048 = 0000000000000000000000000000000000000000000000000000100000000000 

counts 0000000000000000000000000000000000000000000000000002101000000001 

例子：

2560 = 0000000000000000000000000000000000000000000000000000101000000000 
530 = 0000000000000000000000000000000000000000000000000000001000010010 
512 = 0000000000000000000000000000000000000000000000000000001000000000 

counts 0000000000000000000000000000000000000000000000000000103000010010 

目前我使用的是相当明显的，幼稚的做法：

static int bits = sizeof(ulong) * 8; 

public static int[] CommonBits(params ulong[] values) { 
    int[] counts = new int[bits]; 
    int length = values.Length; 

    for (int i = 0; i < length; i++) { 
     ulong value = values[i]; 
     for (int j = 0; j < bits && value != 0; j++, value = value >> 1) { 
      counts[j] += (int)(value & 1UL); 
     } 
    } 

    return counts; 
} 

Answer 1

通过首先对整数进行或运算，然后使用结果确定你需要检查哪些位。您仍然需要遍历每一位，但只能在没有1的位而不是values.Length次的位上迭代一次。

Answer 2

我会领你到古典：Bit Twiddling Hacks ，但你的目标似乎与典型的计数略有不同（即你的“计数”变量是以一种非常奇怪的格式），但也许它会很有用。

Answer 3

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 
} 

请记住，该方法的复杂性是aprox的O（LOG2（N）），其中n是计数在比特的数量，因此对于10二是只需要2个循环

你或许应该采取梅托德计数32位白衣64位算术和应用它的词各占一半，你会采取通过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; 

如果您有支持sse4,3的处理器，则可以使用POPCNT指令。 http://en.wikipedia.org/wiki/SSE4

Answer 4

好让我再次尝试：d

改变每个字节中的64位整数为64位的整数通过在LEF

由N * 8移动每个比特例如

10110101 - > 0000000100000000000000010000000100000000000000010000000000000001 （使用该翻译的查找表）

然后只需将所有东西都以正确的方式求和并且y你有一些无符号的字符整数。

你必须通过8倍，使8 * sumations

（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; 
} 

这redcuce速度比较幼稚implemetaton，原因是其COUTS 8位每次。

编辑：

我固定的代码来执行较快打破较小的整数，但我仍然不能确定字节序 而这只有在工作到256路输入，原因是其使用了无符号的字符数据存储英寸如果你有更长的输入字符串，你可以改变这个代码以保持2^16位计数并减少spped 2

Answer 5

我可以做的最好的办法就是让它变得愚蠢并且展开内部循环......似乎已经将性能削减了一半（大约4秒，而不是处理100个100,000次的8倍） ）...我用一个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++，但完全取决于您的应用程序。对不起，我无法提供更多帮助，也许别人会看到我错过的东西。

更新，一些分析器会话显示稳定的36％的改善。 耸肩我试过了。

Answer 6

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]; 

Answer 7

另一种方法，可能是有利可图的，将打造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. 
} 

算法然后退化为：

• 挑2的右手位关闭的数量。
• 使用它作为一个小整数来索引bitToSubscriptArray。
• 在该数组中，取消第一个整数。这是count数组中元素的数量，需要增加。
• 基于该计数，根据您从bitToSubscript数组中提取的下标，循环遍历行的其余部分，递增计数。
• 一旦完成该循环，将原始数字向右移两位....根据需要冲洗重复。

现在有一个问题，我忽略了，在描述中。实际的下标是相对的。你需要跟踪你在count数组中的位置。每次循环时，都会将两个添加到偏移量。至该偏移量，您可以添加bitToSubscript数组中的相对下标。

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

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

良好的狩猎。

邪恶。

Answer 8

我相信这应该给一个不错的速度提高：

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（需要更多的测试案例）