7

我有两个长度相同的字节数组。我需要在每个字节之间执行 XOR 运算，然后计算位总和。

例如：

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

我需要对字节数组中的每个元素执行相同的操作。

4

9 回答 9

12

使用查找表。XORing 后只有 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];
    }
}

（如果你真的想要，你可以把它变成一种扩展方法......）

请注意方法byte[]中的使用CountBitsAfterXor- 您可以将其IEnumerable<byte>设为更通用，但迭代数组（在编译时已知为数组）会更快。可能只是在显微镜下更快，但是，嘿，你问的是最快的方法:)

我几乎可以肯定实际上将其表达为

public static int CountBitsAfterXor(IEnumerable<byte> data)

在现实生活中，但看看哪个更适合你。

还要注意xor变量的类型为int. 事实上，没有为byte值定义 XOR 运算符，如果你做xor了 a byte，由于复合赋值运算符的性质，它仍然可以编译，但它会在每次迭代中执行一次强制转换——至少在 IL 中是这样。JIT 很可能会处理这个问题，但甚至不需要要求它:)

于 2010-11-18T19:48:00.523 回答
9

最快的方法可能是一个 256 元素的查找表......

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

例如

11110000^01010101 = 10100101 -> lut[165] == 4
于 2010-11-18T19:45:57.017 回答
6

这通常被称为位计数。实际上有几十种不同的算法可以做到这一点。这是一个网站，其中列出了一些更知名的方法。甚至有专门针对 CPU 的指令来执行此操作。

从理论上讲，Microsoft 可以添加一个BitArray.CountSetBits函数，该函数使用该 CPU 架构的最佳算法进行 JITed。一方面，我会欢迎这样的补充。

于 2010-11-18T20:00:32.893 回答
3

据我了解，您希望将左右字节之间的每个 XOR 的位相加。

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?
}
于 2010-11-18T19:44:10.417 回答
3

我不确定您的意思是对字节求和还是对位求和。要将字节内的位相加，这应该有效：

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

然后，您当然需要 xoring 和数组循环。

于 2010-11-18T19:44:48.607 回答
1

以下应该做

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;
}
于 2010-11-18T19:40:44.020 回答
1

它可以重写为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;
}
于 2012-09-18T18:56:15.357 回答
0

计算位的通用函数可能如下所示：

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;
}
于 2011-03-24T13:34:13.377 回答
0

查找表应该是最快的，但是如果您想在没有查找表的情况下执行此操作，那么这将在 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 的位摆弄网站中描述的通用位计数函数的字节版本。

于 2015-11-20T15:57:54.693 回答