2

假设一个大小为 M 的位序列和另一个大小为 N 的位序列，其中 M >> N。M 和 N 都可以保存在整数数组中：如果 N 的长度为 30，那么将需要一个只有一个整数的数组，但如果 N 的长度为 300，则需要一个包含 10 个整数的数组来存储它。

我要做的是在 M 内移动 N，并为 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 位，这也只需要几毫秒。

要“计算并计算 M xor N”，

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 条指令（如果您使用 RCR 指令），可能不值得冒破坏 L1 缓存的风险。

除非您可以使用带有 POPCNT 指令的 Core i7 处理器，否则最重要的部分将是位计数。有关位计数的快速实现，请参阅此页面。

对于较小长度的 N（以机器语言表示），您将通过特殊封装内环来大幅提高速度。对于具有 SSE4.2 的处理器上的 N <= 192 位，它应该能够运行两个最里面的循环，并将所有内容保存在寄存器中。我生锈的 ASM 向我展示了 14 个活动寄存器，其中最内层循环（移位超过 64 位位置）长度为 20 条指令，另外 5 条用于从输入中读取下一个字）。

于 2009-11-05T19:12:34.903 回答