The fastest way to calculate the sum of bits in a byte array

Question

I have two byte arrays with the same length. I need to perform an XOR operation between each byte and after that calculate the sum of the bits.

For example:

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

I need to do the same operation for each element in an byte array.

Answer 1

Use the lookup table. After XORing, there are only 256 possible values, so it will not take much time. Unlike the izb solution, I would not suggest manually placing all the values, at least calculating the lookup table once at startup using one of the response loops.

For example:

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

(You could do this with an extension method if you really wanted to ...)

Note the use of byte[] in the CountBitsAfterXor method - you can make it IEnumerable<byte> for more generality, but iterating over the array (which is known to be an array at compile time) will be faster, probably only microscopically faster, but hey you asked for the fastest way :)

I almost certainly would have expressed it as

 public static int CountBitsAfterXor(IEnumerable<byte> data) 

in real life, but look what is best for you.

Also note the xor variable type as int . In fact, there is no XOR operator for byte values, and if you did xor a byte , it will still compile due to the nature of the compound assignment operators, but it will perform a throw at each iteration - at least in IL. It is possible that JIT will take care of this, but there is no need to even ask for it :)

Answer 2

The fastest way is probably a 256-element lookup table ...

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

eg.

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

Answer 3

This is most often called bit counting. There are literally dozens of different algorithms for this. Here is one site listing some of the best known methods. There are even instructions specific to the CPU for this.

In theory, Microsoft could add the BitArray.CountSetBits function, which gets JITed with the best algorithm for this processor architecture. For example, I would welcome such an addition.

Answer 4

As I understand it, you want to sum the bits of each XOR between left and right bytes.

 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 5

I am not sure if you mean the sum of bytes or bits. To sum the bits in a byte, this should work:

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

For this you will need xoring and a loop cycle around this, of course.

Answer 6

Following should do

 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 7

It can be rewritten as ulong and use the unsafe pointer, but byte easier to understand:

 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 8

A general function for counting bits may look like this:

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

The less than 1 bit, the faster it works. It simply iterates over each byte and switches the least significant bit of that byte until the byte becomes 0. Casting should be necessary so that the compiler stops complaining about extension and type narrowing.

Then your problem can be solved with this:

 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 9

The lookup table should be the fastest, but if you want to do this without a lookup table, this will work for bytes in just 10 operations.

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

This is a byte version of the common bit counting function described on the Sean Eron Anderson bit side .