从8位复制到32位 [英] Bit duplication from 8-bit to 32-bit

问题描述

我正在尝试将8位值复制为32位，并想问问是否有可能编写单行算法来复制位值.

I'm trying to duplicate an 8-bit value to 32-bit and wanted to ask if it's possible to write a single line algorithm to duplicate the bit values.

例如:

1100 1011 -> 1111 1111 0000 0000 1111 0000 1111 1111

如果可能，我想了解其背后的逻辑是什么.

If it's possible, I would like to understand what's the logic behind it.

推荐答案

这很简单-解决最简单的情况，然后执行更复杂的情况.

It's simple - solve the simplest case, then do more complex ones.

您只需要在此之间插入3个零位来扩展位.完成此操作后，最后一步是:

You just need to spread bits by inserting 3 zero bits between then. Once this is done, the final step is:

x = (x << 0) | (x << 1) | (x << 2) | (x << 3);

或者以一种不太明显但更快的方式:

Or in a less obvious but faster way:

x = (x << 4) - x;

情况1:将2位复制为8位值(最简单).

Case 1: Duplicate 2 bits into an 8 bit value (the simplest).

+---+---------+---------+
| 0 | _ _ _ _ | _ _ A B |
+---+---------+---------+
| 1 | _ _ _ A | _ _ _ B |
+---+---------+---------+
| 2 | A A A A | B B B B |
+---+---------+---------+

情况2:将4位复制为16位值.如何?只需将2位移至上部，即可将其变成表壳1！分而治之！

Case 2: Duplicate 4 bits into a 16 bit value. How? Just move 2 bits to the upper part to turn it into the case 1! Divide and conquer!

+---+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D |
+---+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D |
+---+---------+---------+---------+---------+
| 2 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D |
+---+---------+---------+---------+---------+
| 3 | A A A A | B B B B | C C C C | D D D D |
+---+---------+---------+---------+---------+

情况3:将8位复制为32位值(原始值).

Case 3: Duplicate 8 bits into a 32 bit value (the original).

+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | _ _ _ _ | _ _ _ _ | _ _ _ _ | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 2 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D | _ _ _ _ | _ _ E F | _ _ _ _ | _ _ G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 3 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D | _ _ _ E | _ _ _ F | _ _ _ G | _ _ _ H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 4 | A A A A | B B B B | C C C C | D D D D | E E E E | F F F F | G G G G | H H H H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+

可以通过以下代码实现:

Can be achieved by the code below:

uint32_t interleave(uint8_t value)
{
    uint32_t x = value;
    x = (x | (x << 12)) /* & 0x000F000F */; // GCC is not able to remove redundant & here
    x = (x | (x <<  6)) & 0x03030303;
    x = (x | (x <<  3)) & 0x11111111;
    x = (x << 4) - x;
    return x;
}

一些测试用例，以检查其是否有效:

Some test cases to check that it works:

TEST_F(test, interleave)
{
    EXPECT_EQ(interleave(0x00), 0x00000000);
    EXPECT_EQ(interleave(0x11), 0x000F000F);
    EXPECT_EQ(interleave(0x22), 0x00F000F0);
    EXPECT_EQ(interleave(0x33), 0x00FF00FF);
    EXPECT_EQ(interleave(0x44), 0x0F000F00);
    EXPECT_EQ(interleave(0x55), 0x0F0F0F0F);
    EXPECT_EQ(interleave(0x66), 0x0FF00FF0);
    EXPECT_EQ(interleave(0x77), 0x0FFF0FFF);
    EXPECT_EQ(interleave(0x88), 0xF000F000);
    EXPECT_EQ(interleave(0x99), 0xF00FF00F);
    EXPECT_EQ(interleave(0xAA), 0xF0F0F0F0);
    EXPECT_EQ(interleave(0xBB), 0xF0FFF0FF);
    EXPECT_EQ(interleave(0xCC), 0xFF00FF00);
    EXPECT_EQ(interleave(0xDD), 0xFF0FFF0F);
    EXPECT_EQ(interleave(0xEE), 0xFFF0FFF0);
    EXPECT_EQ(interleave(0xFF), 0xFFFFFFFF);

    EXPECT_EQ(interleave(0x01), 0x0000000F);
    EXPECT_EQ(interleave(0x23), 0x00F000FF);
    EXPECT_EQ(interleave(0x45), 0x0F000F0F);
    EXPECT_EQ(interleave(0x67), 0x0FF00FFF);
    EXPECT_EQ(interleave(0x89), 0xF000F00F);
    EXPECT_EQ(interleave(0xAB), 0xF0F0F0FF);
    EXPECT_EQ(interleave(0xCD), 0xFF00FF0F);
    EXPECT_EQ(interleave(0xEF), 0xFFF0FFFF);
}

这篇关于从8位复制到32位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！