2

サイズ M のビット シーケンスと、サイズ N の別のビット シーケンスがあり、M >> N であるとします。M と N の両方を整数配列内に保存できます。N の長さが 30 の場合、整数が 1 つだけの配列が必要になります。ただし、N の長さが 300 の場合、それを格納するには 10 個の整数を含む配列が必要になります。

私がやろうとしているのは、N を M 内にシフトし、M 内の可能な位置 k ごとに、N と M(k) の間の差の数を (XORing によって) 見つけることです。M が 10000 ビットで N が 100 ビットの場合、10000-100=9900 の位置で XOR 比較が実行されます。

それができるライブラリ、またはアルゴリズムを提案できるライブラリを知っていますか? 他の多くの方法で実行できることはわかっていますが、可能な限り最速の方法はここで提案されている方法だと思います。あなたがより速い方法を考えることができるなら、私は提案を受け入れます!

私は C または C++ で何かをしたいと思いますが、他の言語、さらには疑似コードも受け入れられます。

前もって感謝します。

4

3 に答える 3

1

簡単なアプローチ：

while N < M * (original N) do
  compute and tally up M xor N
  multiply each word (unsigned) in N by 2,   // i.e. shift left 1 bit
    and add in the carry (= overflow) from the previous word.

最新のCPUは十分に強力であるため、10,000ビットおよび100ビットの場合でも、これには数ミリ秒しかかかりません。

「MxorNを計算して集計する」には、

sum = 0
for (i=0; i<M/8; i++)
   if M[i] != 0
      w = M[i]
      while w != 0
      if ((w & 1) != 0) sum++   // test LSB
      w /= 2                    // shift right 1 bit

これを最適化する方法はたくさんあります。ほとんどの場合0になる桁がたくさんあり、これらを認識して無視することができます...しかし、上記のアルゴリズムで開始できます。

于 2009-11-05T14:18:56.297 に答える
1

これが完全で実用的なソリューションです。読者のための演習として残されているマイナーなずさんさ:)

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define M_SIZE 100
#define N_SIZE 25
#define bitsToBytes(n) ((n + 7)/8)

typedef unsigned char byte;

void dumpBytes(byte *arr, size_t size) {
   int b;
   for (b=0; b<size; b++) {
      printf("%02x", *arr++);
   }
   printf("\n");
}

int main(int argc, char *argv[]) {

   byte M[bitsToBytes(M_SIZE)], N[bitsToBytes(N_SIZE)];

   /* Fill M and N with random bits */

   int b;

   for (b=0; b<sizeof(M); b++) {
      M[b] = 0xff & rand();
   }
   for (b=0; b<sizeof(N); b++) {
      N[b] = 0xff & rand();
   }

   /* Create a couple of arrays big enough for M_SIZE + N_SIZE, 
      to allow shifting N all the way before the left of M. */
   #define MN_SIZE (M_SIZE + N_SIZE)
   #define MN_BYTES (bitsToBytes(MN_SIZE))
   byte MM[MN_BYTES], NN[MN_BYTES];

   /* Zero out MM, NN, then copy M, N there (right justified). */
   int offset = sizeof(MM) - sizeof(M);
   memset (MM, 0, sizeof(MM)); memcpy(MM+offset, M, sizeof(M));
   offset = sizeof(NN) - sizeof(N);
   memset (NN, 0, sizeof(NN)); memcpy(NN+offset, N, sizeof(N));

   dumpBytes(MM, MN_BYTES);
   /* Count up "difference bits" until NN has been left-shifted into oblivion. */
   int s;
   for (s=0; s<MN_SIZE; s++) {
      int sum = 0;
      for (b=0; b<MN_BYTES; b++) {
  int xor = MM[b] ^ NN[b];
  while (xor != 0) {
     sum += (xor & 1);
     xor >>= 1;
  }
      }
      dumpBytes(NN, MN_BYTES);
      printf("Shift: %4d; bits: %3d.\n", s, sum);
      /* shift NN one bit to the left */
      for (b=0; b<MN_BYTES; b++) {
  NN[b] <<= 1;
  if (b < (MN_BYTES - 1) && ((NN[b+1] & 0x80) != 0)) NN[b] |= 1;
      }
   }
}
于 2009-11-05T18:54:49.050 に答える
1

N を M の上にシフトするか、M を N にシフトすることができます。N をシフトするときに、入力がワード サイズと一致しない場合は、マスクもシフトする必要があります。シフトは、ビット単位のワード サイズの長さで配列にキャッシュできますが、複数のワードにわたるシフトが 1 ワードあたり 1 命令であることを考えると (RCR 命令を使用する場合)、L1 キャッシュをスラッシングするリスクを冒す価値はないかもしれません。

POPCNT 命令を備えた Core i7 プロセッサを当てにすることができない限り、最も重要な部分はとにかくビット カウントになります。ビットカウントの高速実装については、このページを参照してください。

N の長さが短い場合 (機械語で)、内側のループを特別にケーシングすることにより、速度が大幅に向上します。SSE4.2 を搭載したプロセッサーで N <= 192 ビットの場合、すべてをレジスターに保持したまま、最も内側の 2 つのループを実行できるはずです。私のさびた ASM は、入力から次のワードを読み取るための別の 5 つの命令で、最も内側のループ (64 ビット位置をシフトする) の長さが 20 の 14 のライブレジスタを示しています)。

于 2009-11-05T19:12:34.903 に答える