从 8 位到 32 位的位重复

Question

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

例如：

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

如果可以的话，我想了解一下这背后的逻辑是什么

Answer 1

只有 256 个 8 位值，所以简单的查找 table 将占用 1kb，查找是微不足道的。很难相信任何 bithack 都会有卓越的性能。

Answer 2

这可行：

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & 0x80 ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & 0x40 ? 0xf << 24 : 0x0;
    output |= a & 0x20 ? 0xf << 20 : 0x0;
    output |= a & 0x10 ? 0xf << 16 : 0x0;

    output |= a & 0x8 ? 0xf << 12 : 0x0;
    output |= a & 0x4 ? 0xf << 8 : 0x0;
    output |= a & 0x2 ? 0xf << 4 : 0x0;
    output |= a & 0x1 ? 0xf : 0x0;

    return output;
}

或者这个：

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & (1 << 7) ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & (1 << 6) ? 0xf << 24 : 0x0;
    output |= a & (1 << 5) ? 0xf << 20 : 0x0;
    output |= a & (1 << 4) ? 0xf << 16 : 0x0;

    output |= a & (1 << 3) ? 0xf << 12 : 0x0;
    output |= a & (1 << 2) ? 0xf << 8 : 0x0;
    output |= a & (1 << 1) ? 0xf << 4 : 0x0;
    output |= a & 1 ? 0xf : 0x0;

    return output;
}

另一个解决方案：

unsigned int eToTW (unsigned char a) {     
    return (a & 1 << 7 ? ((unsigned) 0xf) << 28 : 0x0) | 
           (a & 1 << 6 ? 0xf << 24 : 0x0) | 
           (a & 1 << 5 ? 0xf << 20 : 0x0) | 
           (a & 1 << 4 ? 0xf << 16 : 0x0) | 
           (a & 1 << 3 ? 0xf << 12 : 0x0) |
           (a & 1 << 2 ? 0xf << 8 : 0x0) |
           (a & 1 << 1 ? 0xf << 4 : 0x0) |
           (a & 1 ? 0xf : 0x0);
}

Answer 3

查找 table，如 will provide the highest performance on most platforms. If you prefer a bit-twiddling approach, the optimal solution will depend on the hardware capabilities of your processor, e.g. how fast are shifts, does it have three-input logic operations (like my GPU), how many integer instructions can it execute in parallel? One solution is to transport each bit to the lsb of its target nibble, then fill in each nibble with its lsb value in a second step (a tip of the hat to chqrlie 中建议使用 lsb 而不是 msb):

#include <stdint.h>
uint32_t expand_bits_to_nibbles (uint8_t x)
{
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = ((((uint32_t)x << (4*0-0)) & (1u << (4*0))) |
         (((uint32_t)x << (4*1-1)) & (1u << (4*1))) |
         (((uint32_t)x << (4*2-2)) & (1u << (4*2))) |
         (((uint32_t)x << (4*3-3)) & (1u << (4*3))) |
         (((uint32_t)x << (4*4-4)) & (1u << (4*4))) |
         (((uint32_t)x << (4*5-5)) & (1u << (4*5))) |
         (((uint32_t)x << (4*6-6)) & (1u << (4*6))) |
         (((uint32_t)x << (4*7-7)) & (1u << (4*7))));
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

Compiler Explorer 的一些快速实验表明，这会导致 particularly efficient code 在 PowerPC64 上，例如。

如果处理器有一个快速的整数乘法器，我们可以用它同时将多个位移位到位。在这里，我们希望使用三个源位组来避免冲突：

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul (uint8_t x)
{
    const uint32_t spread3 = (1u <<  6) | (1u <<  3) | (1u <<  0);
    const uint8_t bits_lo3 = (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_md3 = (1u <<  5) | (1u <<  4) | (1u <<  3);
    const uint8_t bits_hi2 = (1u <<  7) | (1u <<  6);
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) | 
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = (((uint32_t)(x & bits_lo3) * (spread3 <<  0)) +
         ((uint32_t)(x & bits_md3) * (spread3 <<  9)) +
         ((uint32_t)(x & bits_hi2) * (spread3 << 18))) & nib_lsb;
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

另一个使用整数乘法的变体在某些平台上可能更快，它使用了 this answer 中的想法。我们使用乘法一次传播四位，这样它们就会落在目标半字节内。但是，我们必须先将半字节内的位移动到半字节的 lsb，然后才能扩展 lsb 以覆盖半字节。我们可能会以额外的内务处理为代价来节省乘法。

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul2 (uint8_t x)
{
    const uint32_t spread4 = (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t extract = (1u << (3*4+3+16)) | (1u << (2*4+2+16)) | 
                             (1u << (1*4+1+16)) | (1u << (0*4+0+16)) |
                             (1u << (3*4+3+ 0)) | (1u << (2*4+2+ 0)) | 
                             (1u << (1*4+1+ 0)) | (1u << (0*4+0+ 0));
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) |
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t nib_msb = (nib_lsb << 3);
    const uint8_t bits_lo4 = (1u <<  3) | (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_hi4 = (1u <<  7) | (1u <<  6) | (1u <<  5) | (1u <<  4);
    uint32_t r;
    /* spread bits to their target nibbles */
    r = (((uint32_t)(x & bits_lo4) * (spread4 <<  0)) +  
         ((uint32_t)(x & bits_hi4) * (spread4 << 12)));
    /* extract appropriate bit in each nibble and move it into nibble's lsb */
    r = (((r & extract) + (nib_msb - extract)) >> 3) & nib_lsb;
    /* fill in each nibble with its lsb */
    r = (r << 4) - r;
    return r;
}

Answer 4

很简单 - 先解决最简单的问题，然后再解决更复杂的问题。

案例 1：将 1 位复制为 4 位值（最简单）。

+---+---------+
| 0 | _ _ _ A |
+---+---------+
| 1 | A A A A |
+---+---------+

这可以通过一组简单的轮班来完成：

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

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

x = (x << 4) - x;

在以下所有情况下，此步骤将是最后一步。

情况 2：将 2 位复制为 8 位值。

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

情况 3：将 4 位重复为 16 位值。如何？只需将 2 位移动到上半部分即可将其变成案例 1！分而治之！

+---+---------+---------+---------+---------+
| 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 |
+---+---------+---------+---------+---------+

案例 4：将 8 位复制为 32 位值（原始值）。

+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 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 |
+---+---------+---------+---------+---------+---------+---------+---------+---------+

可以通过下面的代码实现：

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;
}

检查其是否有效的一些测试用例：

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 位的位重复

Bit duplication from 8-bit to 32-bit

c

duplicates

bit-manipulation

expansion