位：搜索和替换位序列

Question

我自己是一名高级程序员，我在位运算上遇到了很多困难。我希望我努力实现的目标是可行的？

假设我有一个无符号 8 位整数 - 它可以是任何值。让我们研究两个例子：0xe4 (11100100) 和 0xa5 (10100101).

硬件将这些解释为 4 块：11 10 01 00 和 10 10 01 01。

我正在尝试用纯 C 编写 3 个方法：

将所有 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）

试图搜索位替换方法，但无法解决这个特殊要求。我应该从哪里开始？

Answer 1

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

Answer 2

这里有一些快速、非循环的单行代码，可以满足您的需求：

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 来轻松更改它们以对更多位进行操作实例.

每个函数都硬连接到其特定任务，因此您不能传入任意值。他们的主要优势是速度。

Answer 3

首先，我假设您不打算在单个操作中连续执行这些操作。如果你真的这样做了，不管输入是什么，结果总是 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 中的最低有效位还是更高有效位。不幸的是，这不仅会因平台而异，而且在同一平台上的不同编译器之间也会有所不同。另一方面，在你的情况下，这根本无关紧要。

位：搜索和替换位序列

Bits: Search&Replace bit sequences

c

bit-manipulation

gameboy