計算字節數組總和的最快方法

Question

我有兩個長度相同的字節數組。我需要在每個字節之間執行XOR運算，並在此之後計算總和位數。

例如：

11110000^01010101 = 10100101 -> so 1+1+1+1 = 4 

我需要在字節數組的每個元素執行相同的操作。

Answer 1

使用查找表。異或之後只有256個可能的值，所以不會花費很長時間。雖然不像izb的解決方案，我不會建議手動將所有的值 - 雖然在啓動時使用其中一個循環答案計算查找表一次。

例如：

public static class ByteArrayHelpers 
{ 
    private static readonly int[] LookupTable = 
     Enumerable.Range(0, 256).Select(CountBits).ToArray(); 

    private static int CountBits(int value) 
    { 
     int count = 0; 
     for (int i=0; i < 8; i++) 
     { 
      count += (value >> i) & 1; 
     } 
     return count; 
    } 

    public static int CountBitsAfterXor(byte[] array) 
    { 
     int xor = 0; 
     foreach (byte b in array) 
     { 
      xor ^= b; 
     } 
     return LookupTable[xor]; 
    } 
} 

（您可以使它的擴展方法，如果你真的想...）

注意在CountBitsAfterXor方法使用byte[] - 你能使其更具通用性，但是迭代數組（在編譯時已知是一個數組）會更快。大概只有在顯微鏡下更快，但嘿，你要的最快方式:)

我幾乎肯定會實際上它表示爲

public static int CountBitsAfterXor(IEnumerable<byte> data) 

在現實生活中

，而是看哪個適合你工作得更好。

另請注意xor變量的類型爲int。實際上，沒有爲byte值定義XOR運算符，並且如果您製作xor a byte由於複合賦值運算符的性質，它仍然會編譯，但它將在每次迭代中執行一次強制轉換 - 至少在IL中。JIT很有可能會照顧到這一點，但是甚至不需要問它:)

Answer 2

要總結的左，右字節之間的每個XOR的比特以下應該做

int BitXorAndSum(byte[] left, byte[] right) { 
    int sum = 0; 
    for (var i = 0; i < left.Length; i++) { 
    sum += SumBits((byte)(left[i]^right[i])); 
    } 
    return sum; 
} 

int SumBits(byte b) { 
    var sum = 0; 
    for (var i = 0; i < 8; i++) { 
    sum += (0x1) & (b >> i); 
    } 
    return sum; 
} 

Answer 3

我的理解它。

for (int b = 0; b < left.Length; b++) { 
    int num = left[b]^right[b]; 
    int sum = 0; 

    for (int i = 0; i < 8; i++) { 
    sum += (num >> i) & 1; 
    } 

    // do something with sum maybe? 
} 

Answer 4

我不確定你是指總和字節還是位。 綜上所述一個字節中的位，這應該工作：

int nSum = 0; 
for (int i=0; i<=7; i++) 
{ 
    nSum += (byte_val>>i) & 1; 
} 

你會那麼需要的異或，和陣列環形跑道的解決這個問題，。

Answer 5

最快的方式可能會是一個256元的查找表...

int[] lut 
{ 
    /*0x00*/ 0, 
    /*0x01*/ 1, 
    /*0x02*/ 1, 
    /*0x03*/ 2 
    ... 
    /*0xFE*/ 7, 
    /*0xFF*/ 8 
} 

例如

11110000^01010101 = 10100101 -> lut[165] == 4 

Answer 6

這更通常稱爲位計數。實際上有幾十種不同的算法。 Here是一個網站，列出了一些更爲人熟知的方法。甚至有CPU特定的指令來做到這一點。

從理論上講，微軟可以添加一個BitArray.CountSetBits函數，該函數獲得該CPU架構最佳算法的JIT。舉個例子，我會歡迎這樣的補充。

Answer 7

的一般功能，計數位可能看起來像：

int Count1(byte[] a) 
{ 
    int count = 0; 
    for (int i = 0; i < a.Length; i++) 
    { 
    byte b = a[i]; 
    while (b != 0) 
    { 
     count++; 
     b = (byte)((int)b & (int)(b - 1)); 
    } 
    } 
    return count; 
} 

越少1位，更快的工作原理。它只是循環遍歷每個字節，並切換該字節的最低1位，直到字節變爲0.鑄造是必要的，以便編譯器停止抱怨類型加寬和縮小。

你的問題，然後可以通過使用該解決：

int Count1Xor(byte[] a1, byte[] a2) 
{ 
    int count = 0; 
    for (int i = 0; i < Math.Min(a1.Length, a2.Length); i++) 
    { 
    byte b = (byte)((int)a1[i]^(int)a2[i]); 
    while (b != 0) 
    { 
     count++; 
     b = (byte)((int)b & (int)(b - 1)); 
    } 
    } 
    return count; 
} 

Answer 8

可以改寫爲ulong和使用unsafe指針，但byte是比較容易理解：

static int BitCount(byte num) 
{ 
    // 0x5 = 0101 (bit) 0x55 = 01010101 
    // 0x3 = 0011 (bit) 0x33 = 00110011 
    // 0xF = 1111 (bit) 0x0F = 00001111 
    uint count = num; 
    count = ((count >> 1) & 0x55) + (count & 0x55); 
    count = ((count >> 2) & 0x33) + (count & 0x33); 
    count = ((count >> 4) & 0xF0) + (count & 0x0F); 
    return (int)count; 
} 

Answer 9

的查找表應該是最快的，但是如果你想在沒有查找表的情況下做到這一點，這將在10次操作中用於字節。

public static int BitCount(byte value) { 
    int v = value - ((value >> 1) & 0x55); 
    v = (v & 0x33) + ((v >> 2) & 0x33); 
    return ((v + (v >> 4) & 0x0F)); 
} 

這是在Sean Eron Anderson's bit fiddling site上描述的通用位計數功能的字節版本。