c - 反转位数组中位的顺序

Question

我有一个很长的位序列存储在一个无符号长整数数组中，就像这样

struct bit_array
{
    int size; /* nr of bits */
    unsigned long *array; /* the container that stores bits */
}

我正在尝试设计一种算法来反转 *array 中的位顺序。问题:

• size 可以是任何值，即不一定是 8 或 32 等的倍数，因此输入数组中的第一位可以在输出数组中 unsigned long 中的任何位置结束；
• 该算法应该与平台无关，即适用于任何 sizeof(unsigned long)。

代码、伪代码、算法描述等——任何比暴力(“一点一点”)方法更好的方法都是受欢迎的。

Answer 1

我最喜欢的解决方案是填充一个在单个字节上进行位反转的查找表(因此有 256 个字节条目)。

您将表应用于输入操作数的 1 到 4 个字节，并进行交换。如果大小不是 8 的倍数，则需要通过最后的右移进行调整。

这可以很好地扩展到更大的整数。

例子:

11 10010011 00001010 -> 01010000 11001001 11000000 -> 01 01000011 00100111

要将数字可移植地拆分为字节，您需要使用按位掩码/移位；将结构或字节数组映射到整数可以提高效率。

对于暴力性能，您可以考虑一次最多映射 16 位，但这看起来不太合理。