c - 整数数组的按位异或和移位

Question

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

我想做的是将 N 移到 M 内，并针对 M 内每个可能的位置 k 找到 N 和 M(k) 之间的差异数(通过异或)。如果M有10000位，N有100位，则有10000-100=9900个位置将执行异或比较。

您知道有一个库可以做到这一点或者可以提出一种算法吗？我知道可以通过许多其他方法来完成，但我相信最快的方法就是这里提出的方法。如果您能想到更快的方法，那么我愿意接受建议!

我更喜欢 C 或 C++ 语言，但其他语言，甚至伪代码也是可以接受的。

提前致谢。

Answer 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;
      }
   }
}