7

同じ長さの2バイト配列があります。各バイト間でXOR演算を実行し、この後にビットの合計を計算する必要があります。

例えば：

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

バイト配列の各要素に対して同じ操作を行う必要があります。

4

9 に答える 9

12

ルックアップ テーブルを使用します。XOR 後は 256 の可能な値しかないため、それほど時間はかかりません。ただし、izb のソリューションとは異なり、すべての値を手動で入力することはお勧めしません。起動時に、ループする回答の 1 つを使用してルックアップ テーブルを1 回計算します。

例えば：

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[]での の使用に注意してください。より一般的にすることもできますが、配列 (コンパイル時に配列であることがわかっている) を反復処理する方が高速になります。おそらく微視的に速いだけですが、ねえ、あなたは最速の方法を求めました:)CountBitsAfterXorIEnumerable<byte>

私はほぼ間違いなく実際にそれを次のように表現します

public static int CountBitsAfterXor(IEnumerable<byte> data)

実生活で、どちらがより効果的かを確認してください。

また、xor変数の型をint. byte実際、値に対して定義された XOR 演算子はありません。作成xorした場合byteでも、複合代入演算子の性質によりコンパイルされますが、少なくとも IL では、反復ごとにキャストが実行されます。JITがこれを処理する可能性は十分にありますが、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

これは、より一般的にビットカウントと呼ばれます。これを行うためのアルゴリズムは文字通り数十種類あります。これは、よりよく知られている方法のいくつかをリストしている 1 つのサイトです。これを行うための CPU 固有の命令もあります。

理論的には、Microsoft は、BitArray.CountSetBitsその CPU アーキテクチャに最適なアルゴリズムで JIT される関数を追加できます。私は、そのような追加を歓迎します。

于 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使用することもできますが、理解しやすいです。unsafebyte

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 ビットが少ないほど、これは高速に動作します。各バイトを単純にループし、バイトが 0 になるまでそのバイトの最下位 1 ビットを切り替えます。型の拡大と縮小についてコンパイラが文句を言わないようにするために、キャストが必要です。

次に、これを使用して問題を解決できます。

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 に答える