計算無​​符號長整數中的常見位

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