我需要扫描用于在比特流中的16位的字。 不保证在字节或字边界对齐的。

I need to scan for a 16 bit word in a bit stream. It is not guaranteed to be aligned on byte or word boundaries.

什么是实现这一目标的最快的方法？有各种暴力方法;用表和/或转移，但都没有任何位操作快捷键，可以通过给予肯定的减少计算量/否/也许包含标志结果每个字节或字，因为它到来？

What is the fastest way of achieving this? There are various brute force methods; using tables and/or shifts but are there any "bit twiddling shortcuts" that can cut down the number of calculations by giving yes/no/maybe contains the flag results for each byte or word as it arrives?

C code，内部函数，x86机器code都将是有趣的。

C code, intrinsics, x86 machine code would all be interesting.

推荐答案

我觉得preCALC全部转移字的值，并把它们在16整数 所以你有一个这样的数组

I think precalc all shifted values of the word and put them in 16 ints so you got an array like this

 unsigned short pattern = 1234;
 unsigned int preShifts[16];
 unsigned int masks[16];
 int i;
 for(i=0; i<16; i++)
 {
      preShifts[i] = (unsigned int)(pattern<<i);  //gets promoted to int
      masks[16] = (unsigned int) (0xffff<<i);
 }

，然后你走出流中的每个符号短，使该短和previous短的一个int和unsigned int类型比较的16个无符号整型的。如果其中任何一个匹配，你得到了一个。

and then for every unsigned short you get out of the stream, make an int of that short and the previous short and compare that unsigned int to the 16 unsigned int's. If any of them match, you got one.

所以基本上是这样的：

  int numMatch(unsigned short curWord, unsigned short prevWord)
  {
       int numHits = 0;
       int combinedWords = (prevWord<<16) + curWord;

       int i=0;
       for(i=0; i<16; i++)
       {
             if((combinedWords & masks[i]) == preShifsts[i]) numHits++;
       }
       return numHits;
  }

编辑： 千万注意，这可能意味着多命中时，图案检测不止一次在同一位：

edit: do note that this could potentially mean multiple hits when the patterns is detected more than once on the same bits:

例如。 32位的0和您要检测的模式是16 0的话，那就意味着该模式被检测到16次！

e.g. 32 bits of 0's and the pattern you want to detect is 16 0's, then it would mean the pattern is detected 16 times!