c++ - 高效的位操作

Question

在 C++ 中，我想将 3 个无符号变量的位编码为一个。更准确地说，当三个变量是:

A: a3 a2 a1 a0
B: b3 b2 b1 b0
C: c3 c2 c1 c0

那么输出变量应该包含这样的三元组:

D: a3 b3 c3   a2 b2 c2   a1 b1 c1   a0 b0 c0

让我们假设输出变量对于所有使用的位都足够大。我想到了

unsigned long long result(0);
unsigned a,b,c; // Some numbers to be encoded
for(int level=0;level<numLevels;++level)
{
    int q(1<<level); // SearchBit q: 1<<level
    int baseShift((3*level)-level); // 0,2,4,6
    result|=(   ((a&q)<<(baseShift+2)) | ((b&q)<<(baseShift+1)) | ((c&q)<<(baseShift)) );
}

...而且效果很好。但我想知道是否有一种解决方案不需要循环分别迭代所有位。

Answer 1

定义一个表，将所有或部分位映射到它们的最终位置。适本地移动值。

unsigned long long encoder(unsigned a, unsigned b, unsigned c) {
    static unsigned const encoding[16] = {
        0b0000000000,
        0b0000000001,
        0b0000001000,
        0b0000001001,
        0b0001000000,
        0b0001000001,
        0b0001001000,
        0b0001001001,
        0b1000000000,
        0b1000000001,
        0b1000001000,
        0b1000001001,
        0b1001000000,
        0b1001000001,
        0b1001001000,
        0b1001001001,
    };

    unsigned long long result(0);

    int shift = 0;
    do {
        result += ((encoding[a & 0xF] << 2) | (encoding[b & 0xF] << 1) | encoding[c & 0xF]) << shift;
        shift += 12;
        a >>= 4;
        b >>= 4;
        c >>= 4;
    } while (a || b || c);
    return result;
}

encoding 定义一个表来将 4 位映射到它们的编码位置。这直接用于 c，并为 b 和 a 移动 1 或 2 位。如果要处理的位超过 4 位，源值中接下来的 4 位将向左偏移 12 位。继续这样做，直到处理完所有非零位。

这可以使用 while 循环而不是 do/while 但是在开始之前检查零是没有用的，除非大多数编码都是零值。

如果您经常使用超过 4 位，可以扩展编码表并适当更改循环以一次处理超过 4 位。