Как искать «n бит» в массиве байтов?

Question

У меня есть массив байтов. Теперь мне нужно знать количество появления битовой диаграммы, длина которой равна N.

Например, мой массив байтов «00100100 10010010», а шаблон «001». здесь N = 3, а число равно 5.

Работа с битами всегда слабая.

Answer 1

Вы всегда можете использовать XOR первые N бит, и если вы получите 0, в результате вы получите совпадение. Затем сдвиньте искомый бит «поток» на один бит влево и повторите. Это предполагает, что вы хотите получить совпадения, если эти суб-шаблоны перекрываются. В противном случае вы должны сдвигаться по длине образца по совпадению.

Answer 2

Если предположить, что массив помещается в беззнаковое междунар:

int main() { 
    unsigned int curnum; 
    unsigned int num = 0x2492; 
    unsigned int pattern = 0x1; 
    unsigned int i; 
    unsigned int mask = 0; 
    unsigned int n = 3; 
    unsigned int count = 0; 

    for (i = 0; i < n; i++) { 
     mask |= 1 << i; 
    } 

    for (i = 8 * sizeof(num) - n; i >= 0; i--) { 
     curnum = (num >> i) & mask; 
     if (! (curnum^pattern)) { 
      count++; 
     } 
    } 
} 

Answer 3

Преобразование массива байтов и структуру каждого к std::vector<bool>, а затем вызвать std::search(source.begin(), source.end(), pattern.begin(), pattern.end());. Несмотря на то, что это не работает, это сработает.

Answer 4

Если N может быть сколь угодно большой Вы можете сохранить битовый шаблон в векторе

vector<unsigned char> pattern; 

Размер вектора должен быть

(N + 7)/8 

магазин картина сместилась вправо. Под этим я имею в виду, что, например, если N == 19, Ваш вектор должен выглядеть следующим образом:

|<- v[0] ->|<- v[1] ->|<- v[2] ->| 
0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 
|   |<-    pattern    ->| 

Если у вас есть свой шаблон изначально сдвинут влево, Вы можете использовать функцию я представлю ниже , чтобы сдвинуть биты вправо.

Определите вектор байтов той же длины, что и шаблон, чтобы сохранить часть потока бит для сравнения с шаблоном. Я буду называть его window

vector<unsigned char> window; 

Если N не является целым числом, кратным 8, Вам нужно будет маскировать некоторые левые биты в вашем window, сравнивая его с шаблоном. Вы можете задать маску так:

unsigned char mask = (1 << (N % 8)) - 1; 

Теперь, если предположить, что window содержит биты, она должна, Вы могли бы теоретически сравнить модель с window использованием оператора вектора == как этот

window[0] &= mask; 
bool isMatch = (window == pattern); 

Но есть веские причины быть немного более сложными. Если N велико, и Ваш массив, Вы смотрите шаблон в, значительно больше, это стоит того, чтобы обработать шаблон и построить вектор размера N + 1:

vector<int> shifts; 

Этот вектор будет хранить информацию о том, сколько бит сдвинуть бит-поток, для следующего сравнения, в зависимости от позиции, в которой происходит несоответствие в текущем window.

Рассмотрите образец 0001001100. Вы должны сравнить бит с window справа налево.Если в первом битке есть missmatch, вы знаете, что это 1, и первое вхождение 1 в вашем шаблоне находится в позиции 2, считая форму 0, с правой стороны. Итак, в этом случае, вы знаете, что нет смысла делать сравнение, если количество новых битов, сдвинутых из битового потока, в window меньше 2. Аналогично, если несоответствие происходит на третьем бите (позиция 2 счетная форма 0), window должен быть перемещен на 7, потому что в вашем шаблоне находятся 3 последовательных нули. Если несоответствие находится в позиции 4, вы можете переместить window на 8 и так далее. Вектор sifts с индексом i будет содержать количество бит, с помощью которого можно переместить window, если несоответствие происходит в позиции i. Если есть совпадение, window следует перемещать на число бит, хранящихся в shifts[N]. В приведенном выше примере совпадение означает сдвиг на 8.

На практике, конечно, вы сравниваете целые байты с шаблоном с байтами из window (форму справа налево), и если существует несоответствие, которое вы изучаете бит в байте, чтобы найти положение несоответствия.

if(window[i] != pattern[i]) 
{ 
    int j = 0; 
    unsigned char mismatches = window[i]^pattern[i]; 
    while((mismatches & 1) == 0) 
    { 
     mismatches >>= 1; 
     ++j; 
    } 
    mismatch_position = 8 * (window.size() - i - 1) + j; 
} 

Вот функция, которая может пригодиться, когда вам нужно переместить некоторые биты из вашего потока битов в window. Я написал его в C#, но преобразование в C++ должно быть тривиальным. C# делает некоторые приведения необходимыми, которые, вероятно, не нужны в C++. Используйте unsigned char вместо byte, vector<unsigned char> & вместо byte [], size() вместо Length и, возможно, еще несколько мелких настроек. Функция, вероятно, немного более общая, чем необходимо в вашем сценарии, поскольку она не использует тот факт, что последовательные вызовы извлекают последовательные куски вашего массива байтов, что, возможно, может сделать это немного проще, но я не думаю, что это болит. В текущей форме он может извлекать произвольную битовую подстроку из массива байтов.

public static void shiftBitsIntoWindow_MSbFirst(byte[] window, byte[] source, 
               int startBitPosition, int numberOfBits) 
{ 
    int nob = numberOfBits/8; 
    // number of full bytes from the source 

    int ntsh = numberOfBits % 8; 
    // number of bits, by which to shift the left part of the window, 
    // in the case, when numberOfBits is not an integer multiple of 8 

    int nfstbb = (8 - startBitPosition % 8); 
    // number Of bits from the start to the first byte boundary 
    // The value is from the range [1, 8], which comes handy, 
    // when checking if the substring of ntsh first bits 
    // crosses the byte boundary in the source, by evaluating 
    // the expression ntsh <= nfstbb. 

    int nfbbte = (startBitPosition + numberOfBits) % 8; 
    // number of bits from the last byte boundary to the end 

    int sbtci; 
    // index of the first byte in the source, from which to start 
    // copying nob bytes from the source 
    // The way in which the (sbtci) index is calculated depends on, 
    // whether nob < window.Length 

    if(nob < window.Length)// part of the window will be replaced 
    // with bits from the source, but some part will remain in the 
    // window, only moved to the beginning and possibly shifted 
    { 
     sbtci = (startBitPosition + ntsh)/8; 

     //Loop below moves bits form the end of the window to the front 
     //making room for new bits that will come form the source 

     // In the corner case, when the number by which to shift (ntsh) 
     // is zero the expression (window[i + nob + 1] >> (8 - ntsh)) is 
     // zero and the loop just moves whole bytes 
     for(int i = 0; i < window.Length - nob - 1; ++i) 
     { 
      window[i] = (byte)((window[i + nob] << ntsh) 
       | (window[i + nob + 1] >> (8 - ntsh))); 
     } 

     // At this point, the left part of the window contains all the 
     // bytes that could be constructed solely from the bytes 
     // contained in the right part of the window. Next byte in the 
     // window may contain bits from up to 3 different bytes. One byte 
     // form the right edge of the window and one or two bytes form 
     // the source. If the substring of ntsh first bits crosses the 
     // byte boundary in the source it's two. 

     int si = startBitPosition/8; // index of the byte in the source 
     // where the bit stream starts 

     byte byteSecondPart; // Temporary variable to store the bits, 
     // that come from the source, to combine them later with the bits 
     // form the right edge of the window 

     int mask = (1 << ntsh) - 1; 
     // the mask of the form 0 0 1 1 1 1 1 1 
     //       |<- ntsh ->| 

     if(ntsh <= nfstbb)// the substring of ntsh first bits 
     // doesn't cross the byte boundary in the source 
     { 
      byteSecondPart = (byte)((source[si] >> (nfstbb - ntsh)) & mask); 
     } 
     else// the substring of ntsh first bits crosses the byte boundary 
     // in the source 
     { 
      byteSecondPart = (byte)(((source[si] << (ntsh - nfstbb)) 
            | (source[si + 1] >> (8 - ntsh + nfstbb))) & mask); 
     } 

     // The bits that go into one byte, but come form two sources 
     // -the right edge of the window and the source, are combined below 
     window[window.Length - nob - 1] = (byte)((window[window.Length - 1] << ntsh) 
               | byteSecondPart); 

     // At this point nob whole bytes in the window need to be filled 
     // with remaining bits form the source. It's done by a common loop 
     // for both cases (nob < window.Length) and (nob >= window.Length) 

    } 
    else// !(nob < window.Length) - all bits of the window will be replaced 
    // with the bits from the source. In this case, only the appropriate 
    // variables are set and the copying is done by the loop common for both 
    // cases 
    { 
     sbtci = (startBitPosition + numberOfBits)/8 - window.Length; 
     nob = window.Length; 
    } 


    if(nfbbte > 0)// The bit substring coppied into one byte in the 
    // window crosses byte boundary in the source, so it has to be 
    // combined form the bits, commming form two consecutive bytes 
    // in the source 
    { 
     for(int i = 0; i < nob; ++i) 
     { 
      window[window.Length - nob + i] = (byte)((source[sbtci + i] << nfbbte) 
       | (source[sbtci + 1 + i] >> (8 - nfbbte))); 
     } 
    } 
    else// The bit substring coppied into one byte in the window 
    // doesn't cross byte boundary in the source, so whole bytes 
    // are simply coppied 
    { 
     for(int i = 0; i < nob; ++i) 
     { 
      window[window.Length - nob + i] = source[sbtci + i]; 
     } 
    } 
}