c++ - 有效地删除字节数组中的低半字节 - C++

Question

我有一个长字节数组，我想删除每个字节的低半字节(低 4 位)并将其余部分移动到一起，以便结果占据输入空间的一半。

例如，如果我的输入是057ABC23，我的输出应该是07B2。

我目前的做法是这样的:

// in is unsigned char*
size_t outIdx = 0;
for(size_t i = 0; i < input_length; i += 8) 
{
    in[outIdx++] = (in[i    ] & 0xF0) | (in[i + 1] >> 4);
    in[outIdx++] = (in[i + 2] & 0xF0) | (in[i + 3] >> 4);
    in[outIdx++] = (in[i + 4] & 0xF0) | (in[i + 5] >> 4);
    in[outIdx++] = (in[i + 6] & 0xF0) | (in[i + 7] >> 4);
}

...我基本上在每个循环中处理 8 个字节的输入，以说明我可以假设 input_length 可以被 8 整除(尽管它可能不比每个循环只处理 2 个字节快环形)。该操作就地完成，覆盖输入数组。

有没有更快的方法来做到这一点？例如，因为我一次可以读取 8 个字节，所以可以对 4 字节或 8 字节整数而不是单个字节进行操作，但我想不出这样做的方法。编译器本身也没有想出一些东西，因为我可以看到输出代码仍然对字节进行操作(-O3 似乎做了一些循环展开，但仅此而已)。

我无法控制输入，所以我不能以不同的方式存储它。

Answer 1

有一种通用的位摆弄技术来交换位。假设您有一个 64 位数字，包含以下半字节:

HxGxFxExDxCxBxAx

这里的 x 我表示一个半字节，它的值不重要(你想删除它)。位运算的结果应该是一个 32 位数字 HGFEDCBA。

首先，删除所有的 x 半字节:

HxGxFxExDxCxBxAx & *_*_*_*_*_*_*_*_ = H_G_F_E_D_C_B_A_

为了清楚起见，这里我用 _ 表示 0，用 * 表示二进制 1111。

现在，复制您的数据:

H_G_F_E_D_C_B_A_ << 4 = _G_F_E_D_C_B_A__
H_G_F_E_D_C_B_A_ | _G_F_E_D_C_B_A__ = HGGFFEEDDCCBBAA_

注意您的一些目标半字节是如何组合在一起的。您需要保留这些地方，并删除重复的数据。

HGGFFEEDDCCBBAA_ & **__**__**__**__ = HG__FE__DC__BA__

从这里，您可以直接提取结果字节，或者对该技术进行另一次或两次迭代。

下一次迭代:

HG__FE__DC__BA__ << 8 = __FE__DC__BA____
HG__FE__DC__BA__ | __FE__DC__BA____ = HGFEFEDCDCBABA__
HGFEFEDCDCBABA__ & ****____****____ = HGFE____DCBA____

上次迭代:

HGFE____DCBA____ << 16 = ____DCBA________
HGFE____DCBA____ | ____DCBA________ = HGFEDCBADCBA____
HGFEDCBADCBA____ >> 32 = ________HGFEDCBA