我有两个长度相同的字节数组。我需要对每个字节执行XOR操作，然后计算位数之和。
例如：
11110000^01010101 = 10100101 -> so 1+1+1+1 = 4
我需要对字节数组中的每个元素执行相同的操作。
9个回答
14
使用查找表。在进行异或运算后，只有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[] - 你也可以将其改成IEnumerable<byte>以实现更多的通用性，但是在编译时已知的数组迭代速度会更快。虽然这个速度上的差别微乎其微，但是毕竟你要求的是最快的方式 :)
我几乎肯定会实际上将它表达为
public static int CountBitsAfterXor(IEnumerable<byte> data)
在现实生活中可能会有不同情况，请自行决定哪种方法更好。
同时要注意xor变量的类型为int。事实上，对于byte值，没有定义XOR运算符，如果将xor声明为byte类型，由于复合赋值运算符的性质，它仍然可以编译通过，但是在每次迭代时都会执行一次强制转换 - 至少在IL中是这样的。 JIT很可能会处理这个问题，但甚至没有必要让它去做 :)
- Jon Skeet
8
最快的方法可能是使用一个256元素的查找表...
int[] lut
{
/*0x00*/ 0,
/*0x01*/ 1,
/*0x02*/ 1,
/*0x03*/ 2
...
/*0xFE*/ 7,
/*0xFF*/ 8
}
e.g.
11110000^01010101 = 10100101 -> lut[165] == 4
- izb
1
1+1 Nabbits。我正要发布这个——你的隐式并行技能非常出色 :-) - user166390
7
这更常被称为比特计数。有着几十种不同的算法来实现这一点。这里是一个列举了一些较为知名的方法的网站。甚至有针对特定CPU的指令来实现此功能。
从理论上讲，Microsoft可以添加一个
从理论上讲，Microsoft可以添加一个
BitArray.CountSetBits函数，并使用最佳算法对该CPU架构进行JIT编译。我个人会欢迎这样的添加。- Brian Gideon
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?
}
- Ron Warholic
1
1如果性能是一个考虑因素，您可能希望预先计算每个256个可能字节组合的位和，并将它们存储在查找表中。我认为这会提高性能，但您需要进行基准测试。 - eoldre
3
我不确定您是指对字节还是位进行求和。 如果要对字节内的位进行求和，可以使用以下方法：
int nSum = 0;
for (int i=0; i<=7; i++)
{
nSum += (byte_val>>i) & 1;
}
你需要进行异或操作，并在此基础上循环数组。
- winwaed
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;
}
- JaredPar
3
这个程序将字节相加。我理解OP的意思是他想要位被相加？ - winwaed
嗨。谢谢回答。但我需要位数之和，不是简单的总和。请看我上面的例子。 - Andrew Orsich
@winaed，@Bugai13，我的错。已更新。 - JaredPar
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;
}
- litfal
1
1第三个计算中有一个错别字，移位后0xF0掩码是错误的，应该使用0x0F掩码。 - Zarat
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;
}
- parvus
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的位操作网站中有描述。
- hatchet - done with SOverflow
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接