反转位的顺序在一个位阵列 [英] Reverse the order of bits in a bit array

问题描述

我有存储在无符号长整数数组，这样的位长序列

I have a long sequence of bits stored in an array of unsigned long integers, like this

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

我想设计一个算法，以扭转*阵位的顺序。问题：

I am trying to design an algorithm to reverse the order of bits in *array. Problems:

• 尺寸可以是任何东西，即不一定是8或32等多种，所以输入数组中的第一位能够在内部的unsigned long类型的任何位置结束输出数组中;


• 的算法应该是平台无关的，即任何工作的sizeof（无符号长）。

• size can be anything, i.e. not necessarily a multiple of 8 or 32 etc, so the first bit in the input array can end up at any position within the unsigned long in the output array;
• the algorithm should be platform-independent, i.e. work for any sizeof(unsigned long).

code，伪code，算法中描述等等 - 任何比暴力破解更好的（点滴）的做法是值得欢迎的。

Code, pseudocode, algo description etc. -- anything better than bruteforce ("bit by bit") approach is welcome.

推荐答案

我最喜欢的解决方案是，以填补查找表，做一个单字节（因此256字节的条目）。

My favorite solution is to fill a lookup-table that does bit-reversal on a single byte (hence 256 byte entries).

您应用表1至4字节的输入操作数，以互换。如果大小不是8的倍数，则需要通过最后的右移来调整。

You apply the table to 1 to 4 bytes of the input operand, with a swap. If the size isn't a multiple of 8, you will need to adjust by a final right shift.

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

This scales well to larger integers.

例如：

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

要移植地分割成数个字节，则需要使用屏蔽位运算/班;一个结构或字节数组到整数的映射可以使之更有效率。

To split the number into bytes portably, you need to use bitwise masking/shifts; mapping of a struct or array of bytes onto the integer can make it more efficient.

有关暴力的表现，你能想到的映射到一次16位的，但这并不看起来相当合理的。

For brute performance, you can think of mapping up to 16 bits at a time, but this doesn't look quite reasonable.

这篇关于反转位的顺序在一个位阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！