反转位数组中的位顺序

Question

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

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

我试图设计一种算法来反转*数组中的位顺序.问题:

• size 可以是任何东西,即不一定是8或32等的倍数,因此输入数组中的第一位可以在输出数组中的无符号长整数内的任何位置结束;
• 算法应该是平台无关的,即适用于任何sizeof(unsigned long).

代码,伪代码,算法描述等 - 比bruteforce("一点一滴")方法更好的方法是受欢迎的.

Answer 1

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

您将表应用于输入操作数的1到4个字节,并使用交换.如果大小不是8的倍数,则需要通过最终右移来调整.

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

例:

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

要将数字拆分为可移植的字节,您需要使用按位屏蔽/移位; 将结构或字节数组映射到整数可以使其更有效.

对于粗暴的性能,您可以考虑一次最多映射16位,但这看起来不太合理.

Answer 2

我喜欢查找表的想法.它仍然是log(n)组位技巧的典型任务,可能非常快.喜欢:

unsigned long reverseOne(unsigned long x) {
  x = ((x & 0xFFFFFFFF00000000) >> 32) | ((x & 0x00000000FFFFFFFF) << 32);
  x = ((x & 0xFFFF0000FFFF0000) >> 16) | ((x & 0x0000FFFF0000FFFF) << 16);
  x = ((x & 0xFF00FF00FF00FF00) >> 8)  | ((x & 0x00FF00FF00FF00FF) << 8);
  x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4)  | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
  x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2)  | ((x & 0x3333333333333333) << 2);
  x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1)  | ((x & 0x5555555555555555) << 1);
  return x;
}

根本的想法是,当我们的目标是颠倒某个序列的顺序时,我们可以交换该序列的头部和尾部,然后分别反转每一半(这里通过递归地对每一半应用相同的过程来完成).

这是一个更便携的版本,支持unsigned long4,8,16或32字节的宽度.

#include <limits.h>

#define ones32 0xFFFFFFFFUL
#if (ULONG_MAX >> 128)
#define fill32(x) (x|(x<<32)|(x<<64)|(x<<96)|(x<<128)|(x<<160)|(x<<192)|(x<<224))
#define patt128 (ones32|(ones32<<32)|(ones32<<64) |(ones32<<96))
#define patt64  (ones32|(ones32<<32)|(ones32<<128)|(ones32<<160))
#define patt32  (ones32|(ones32<<64)|(ones32<<128)|(ones32<<192))
#else
#if (ULONG_MAX >> 64)
#define fill32(x) (x|(x<<32)|(x<<64)|(x<<96))
#define patt64  (ones32|(ones32<<32))
#define patt32  (ones32|(ones32<<64))
#else
#if (ULONG_MAX >> 32)
#define fill32(x) (x|(x<<32))
#define patt32  (ones32)
#else
#define fill32(x) (x)
#endif
#endif
#endif

unsigned long reverseOne(unsigned long x) {
#if (ULONG_MAX >> 32)
#if (ULONG_MAX >> 64)
#if (ULONG_MAX >> 128)
  x = ((x & ~patt128) >> 128) | ((x & patt128) << 128);
#endif
  x = ((x & ~patt64) >> 64) | ((x & patt64) << 64);
#endif
  x = ((x & ~patt32) >> 32) | ((x & patt32) << 32);
#endif
  x = ((x & fill32(0xffff0000UL)) >> 16) | ((x & fill32(0x0000ffffUL)) << 16);
  x = ((x & fill32(0xff00ff00UL)) >> 8)  | ((x & fill32(0x00ff00ffUL)) << 8);
  x = ((x & fill32(0xf0f0f0f0UL)) >> 4)  | ((x & fill32(0x0f0f0f0fUL)) << 4);
  x = ((x & fill32(0xccccccccUL)) >> 2)  | ((x & fill32(0x33333333UL)) << 2);
  x = ((x & fill32(0xaaaaaaaaUL)) >> 1)  | ((x & fill32(0x55555555UL)) << 1);
  return x;
}

Answer 3

在可以在此处找到的相关主题集合中，单个数组条目的位可以按如下方式反转。

unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

之后可以通过重新排列各个位置来反转整个阵列。