Биты: поиск и замена битовых последовательностей - PullRequest
Новая
       57

Биты: поиск и замена битовых последовательностей

0 голосов
/ 16 марта 2020

Будучи программистом высокого уровня, я много борюсь с побитовыми операциями. Я надеюсь, что то, что я пытаюсь достичь, выполнимо?

Допустим, у меня есть одно 8-разрядное целое число без знака - оно может иметь любое значение. Давайте поработаем над двумя примерами: 0xe4 (11100100) и 0xa5 (10100101).

Аппаратное обеспечение интерпретирует их как 4 chunks : 11 10 01 00 и 10 10 01 01.

Я пытаюсь написать 3 метода в чистом виде C:

  • Заменить все 00 чанков на 01 чанк. (результат: 11 10 01 01 и 10 10 01 01)
  • Заменить все 01 куски на 10 кусков. (результат: 11 10 10 10 и 10 10 10 10)
  • Заменить все 10 фрагментов на 11 фрагментов. (результат: 11 11 11 11 и 11 11 11 11)

Пытался искать заменяющие бит методы, но не мог согнуть ни одного, чтобы выполнить это конкретное требование. С чего мне начать?

Ответы [ 3 ]

3 голосов
/ 16 марта 2020

Вот несколько быстрых однополосных однолинейных строк, которые делают то, что вы хотите: 

unsigned set_00_to_01(unsigned x) {
    return x + ((~x >> 1) & ~x & 0x55);
}

unsigned set_01_to_10(unsigned x) {
    return x + ((~x >> 1) & x & 0x55);
}

unsigned set_10_to_11(unsigned x) {
    return x + ((x >> 1) & ~x & 0x55);
}

Обратите внимание, что они работают только с младшими 8 битами, но их можно легко изменить для работы на большее, изменив, например, значения 0x55 на 0x5555 или 0x55555555.

Каждая функция жестко связана с заданной ей задачей c, поэтому вы не можете передавать произвольные значения. Их главное преимущество - скорость.

1 голос
/ 16 марта 2020

Прежде всего, я собираюсь предположить, что вы не планируете выполнять эти операции последовательно в одной операции. Если вы действительно сделаете это, результат всегда будет 0xff, независимо от ввода, поэтому вам не нужно разбираться с вводом, разбивая его на поля или многое другое. Итак, я собираюсь предположить, что если пара битов на входе начиналась с 00, то конечный результат для этого поля должен быть 01, аналогично, если это было 01, оно должно заканчиваться как 10, а если это было 10, это должно в итоге получится 11 (потом, вы можете вызвать его снова, чтобы каждый делал следующий шаг и т. д.).

Во-вторых, я хочу отметить, что эти операции аналогичны простому приращению 2 -битное поле. То есть: 0-> 1, 1-> 2, 2-> 3 (и 3, мы, вероятно, оставим в покое, хотя вы не указали).

Один простой способ добраться до нескольких бит в тип данных C должен использовать поддержку битовых полей. В этом случае мы будем использовать его вместе с объединением, поэтому у нас есть один член объединения, который дает нам доступ к отдельным полям, а другой - ко всему байту как к единице. 

#include <stdio.h>

// depending on how new it is, your compiler may already define this:
typedef unsigned char uint8_t;

struct Foo {
    uint8_t a : 2;
    uint8_t b : 2;
    uint8_t c : 2;
    uint8_t d : 2;
};

typedef union { 
    unsigned char whole;
    struct Foo parts;
} val;

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

int main(void) {
    val a = {.whole = 0xe4};

    // replacing 00 with 01, 01 with 10 and 10 with 11 is incrementing, except for 11
    if (a.parts.a < 3)
        ++a.parts.a;
    if (a.parts.b < 3)
        ++a.parts.b;
    if (a.parts.c < 3)
        ++a.parts.c;
    if (a.parts.d < 3)
        ++a.parts.d;

    printf("%2.2x\n", a.whole);
}

Предупреждение: теоретически, запись в одно поле объединения, а затем чтение из другого не дает определенных результатов. В действительности, однако, код, который взаимодействует с оборудованием, делает подобные вещи довольно регулярно. Что меняется, так это порядок - будь то (например) a.parts.a младший или более значащий бит в a.whole. К сожалению, это может варьироваться не только в зависимости от платформы, но и между разными компиляторами на одной платформе. С другой стороны, в вашем случае это просто не имеет значения.

0 голосов
/ 16 марта 2020 
unsigned replace2Bits(unsigned haystack, unsigned search, unsigned replace, unsigned numchunks)
{
    unsigned mask = 3;
    while(numchunks--)
    {
        if((haystack & mask) == search)
        {
            haystack &= ~mask;
            haystack |= replace;
        }
        mask <<= 2;
        search <<= 2;
        replace <<= 2;
    }
    return haystack;
}

void printbin(unsigned x)
{
    for(unsigned bit = 0x80; bit; bit >>= 1)
    {
        putchar((x & bit) ? '1':'0' );
    }
}

int main()
{
    unsigned char hs1 = 0xe4;
    unsigned char hs2 = 0xa5;

    printbin(hs1);putchar(' ');printbin(hs1 = replace2Bits(hs1,0b00, 0b01, 4)); putchar(' ');
    putchar(' ');printbin(hs1 = replace2Bits(hs1,0b01, 0b10, 4)); putchar(' ');
    putchar(' ');printbin(replace2Bits(hs1,0b10, 0b11, 4)); putchar('\n');

    printbin(hs2);putchar(' ');printbin(hs2 = replace2Bits(hs2,0b00, 0b01, 4)); putchar(' ');
    putchar(' ');printbin(hs2 = replace2Bits(hs2,0b01, 0b10, 4)); putchar(' ');
    putchar(' ');printbin(replace2Bits(hs2,0b10, 0b11, 4)); putchar('\n');
}

https://godbolt.org/z/dcsuuD

...