Упражнение 6 из главы 11 Программирование на C Kochan, поиск битовых комбинаций

Question

Надеясь на некоторую помощь с побитовыми операторами. Упражнение гласит следующее:

Напишите функцию с именем bitpat_search(), которая ищет вхождение указанного шаблона битов внутри целого без знака. Функция должна принимать три аргумента и должна вызываться как таковая:

   bitpat_search (source, pattern, n)

Функция ищет целое число "источник", начиная с крайнего левого бита, чтобы определить, присутствуют ли самые правые n бит "шаблона" в "источнике". Если шаблон найден, пусть функция возвращает номер бита, с которого начинается шаблон, где крайний левый бит равен 0. Если шаблон не найден, то функция возвращает -1. Так, например, вызов

   index = bitpat_search (0xe1f4, 0x5, 3);

заставляет функцию bit_pat(search() искать число 0xe1f4 (= 1110 0001 1111 0100 двоичное) для поиска трехбитового шаблона 0x5 (= 101 двоичного). Функция возвращает 11, чтобы указать, что шаблон был найден в "источник", начиная с бита № 11.

Убедитесь, что функция не делает никаких предположений о размере int.

У меня есть несколько проблем с этим:

1. На самом деле числа не имеют большого смысла для меня... Я пробовал все виды функций printf() после каждой итерации, и похоже, что число 0x5 читается как двоичный код 100, а это будет четыре. Если я попробую другие числа, они просто получаются довольно случайными, но часто равными 000, так что... не очень полезно. Я считаю их неправильно? Изменяет ли правый сдвиг это как-то?

2 - он возвращает неправильную позицию (19, а не 11), но пока я путаю числа, как в моем q1 выше, это не сработает, не так ли?

Извините, если это очевидно для всех вас, милые люди, я просто вижу это. (Я просто пытаюсь извлечь уроки из книги, кстати, это не домашняя работа из школы).

Спасибо

#include <stdio.h>

int int_size(unsigned int num);
int bit_test(unsigned int word, int position, int size);
int bitpat_search(unsigned int source, unsigned int pattern, int n);

int main(void)
{
    int index;

    index  = bitpat_search(0xe1f4, 0x5, 3);

    printf(" Pattern found in position %i\n", index);
    return 0;
}

int bitpat_search(unsigned int source, unsigned int pattern, int n)
{
    int i, j, tempSource, tempPat, count;

    int size = int_size(~0);

    for (i = 0; i < size;)
    {
        count = 0;
        for (j = 0; j < n; j++)
        {
            tempSource = bit_test(source, i, size);
            tempPat = bit_test(pattern, j, size);

            i++;
            count++;

            if (tempSource != tempPat)
            break;
        }
        if (count == n)
            return i - n;
    }
    return 0;

}

int bit_test(unsigned int word, int position, int size)
{
    if( (word >> (size - position)) & 0x1) // shift bits in word 31 minus n     spaces right, and AND word with hexadecimal 1
        return 1; // if above is true (1 & 1) return 1
    else
        return 0;

}

int int_size(unsigned int num)
{
    int size = 0;

    while (num)
    {
        size++;
        num >>= 1;
    }

    return size;
}

Answer 1

1. На самом деле числа не имеют большого смысла для меня... Я пробовал все виды функций printf() после каждой итерации, и похоже, что число 0x5 читается как двоичный код 100, а это будет четыре. Если я попробую другие числа, они просто получаются довольно случайными, но часто равными 000, так что... не очень полезно. Я считаю их неправильно?

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

Изменяет ли правый сдвиг это как-то?

Операторы сдвига оставляют свои операнды без изменений. Конечно, если правый операнд соответствующей операции сдвига не равен нулю, то результат отличается от левого операнда. Если левый операнд получен из переменной, вы можете перезаписать значение этой переменной позже.

2 - он возвращает неправильную позицию (19, а не 11), но пока я путаю числа, как в моем q1 выше, это не сработает, не так ли?

Я не думаю, что ваша главная проблема - "испортить цифры". Ваша реализация проблематична. Рассмотрим гнездо цикла ключей в вашем коде:

for (i = 0; i < size;)
{
    count = 0;
    for (j = 0; j < n; j++)
    {
        tempSource = bit_test(source, i, size);
        tempPat = bit_test(pattern, j, size);

        i++;
        count++;

Заметьте, что вы увеличиваете управляющую переменную внешнего цикла на каждой итерации внутреннего цикла. В результате вы тестируете шаблон только против каждого n^й начальный индекс в исходной строке. То есть вы тестируете неперекрывающиеся наборы исходных битов. Вместо этого вы должны проверить весь шаблон, начиная с каждой возможной начальной позиции.

Также обратите внимание, что вы тестируете начальные n-bit шаблон не может начаться, потому что там меньше, чем n биты между этой позицией и концом строки источника. В этом случае вы в конечном итоге вызовете неопределенное поведение, используя недопустимый правый операнд для оператора сдвига.

Answer 2

for (i = 0; i < size;)
{
    count = 0;
    for (j = 0; j < n; j++)
    {
        tempSource = bit_test(source, i, size);
        tempPat = bit_test(pattern, j, size);

Здесь вы немного проверяете позицию i в источнике против немного в положении j в шаблоне. Это должно быть i+j в источнике, в противном случае вы сравниваете образец с одним битом, а не образец с количеством битов в источнике. Поскольку шаблон 101 содержит единицы и ноль, вы никогда ничего не найдете.

Примечание: вы можете заменить int_size функция по sizeof(int)*8, Это предполагает 8-битные байты, но компьютеры, для которых это предположение не выполняется, не были созданы с начала восьмидесятых годов, так что это должно быть довольно безопасным предположением.

Answer 3

В предлагаемом алгоритме, кроме выявленной проблемы @WouterVerhelst, существуют другие проблемы, приводящие к неверному результату.

Выпуск 1 - В функции bit_test()проверенный бит не является ожидаемым.

Чтобы проверить немного с левой стороны, замените (size - position) от (size - (position + 1)),

int bit_test(unsigned int word, int position, int size)
{
    if( (word >> (size - (position + 1))) & 0x1) // 
        return 1; // if above is true (1 & 1) return 1
    else
        return 0;
}

Выпуск 2 - Будет проверен как тот же размер source, pattern должны быть выровнены по левому краю.

в bitpat_search()перед циклом for, сдвиг влево от (size-n) биты.

int size = int_size(source);

pattern = pattern << (size-n);

Проблема 3 - Чтобы иметь правильный count сравнивать с n, сравнение битов с break; должно быть сделано до count++,

    if (tempSource != tempPat)
        break;

    count++;

Проблема 4 - Возвращенный результат индекса будет i вместо i - n (связано с выпуском 5).

if (count == n)
    return (i); // instead of (i - n);

Проблема 5 - Как предполагает @WouterVerhelst, сравнение между source а также pattern должно быть сделано для каждого бита.

for (i = 0; i < size;i++) // each bit ==> i++
{
    count = 0;
    for (j = 0; j < n; j++)
    {
        tempSource = bit_test(source, i+j, size);
        tempPat = bit_test(pattern, j, size);
        // not here i++;

        if (tempSource != tempPat)
            break;

        count++;
    }
    if (count == n)
        return (i);
}

Проблема 6 - И результат в случае 'шаблон не найден' -1.

return (-1); // Instead of (0);