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

Question

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

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

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

我更喜欢 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;
      }
   }
}

Answer 2

简单的方法：

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，你可以识别并忽略这些......但上面的算法应该可以帮助你入门。

Answer 3

您可以将 N 向上移动到 M 上，或者将 M 向下移动到 N 上。移动 N 时，如果输入与字大小不对齐，您还需要移动掩码。移位可以缓存到长度为字大小（以位为单位）的数组中，但考虑到跨多个字的移位是每个字 1 条指令（如果使用 RCR 指令），可能不值得冒破坏 L1 缓存的风险。

除非您可以依靠带有 POPCNT 指令的 Core i7 处理器，否则最重要的部分无论如何都是位计数。请参阅此页面以快速实现位计数。

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