反转位数组中的位顺序

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

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

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

• size可以是任何东西，即不一定是8或32等的倍数，因此输入数组中的第一位可以在输出数组中的unsigned long内的任何位置结束;
• 算法应该是平台无关的，即适用于任何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; } 

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

这是一个更便携的版本，支持4,8,16或32字节的unsigned long宽度。

 #include  #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 

之后可以通过重新排列各个位置来完成整个arrays的反转。

Answer 4

您必须定义unsigned long整数中的位顺序。 您可以假设位n对应于array[x] & (1 << n)但这需要指定。 如果是这样，如果要使用数组作为字节而不是unsigned long，则需要处理字节顺序（小端或大端）。

我肯定会首先实施蛮力并测量速度是否是一个问题。 如果在大型arrays上没有大量使用，则无需浪费时间尝试优化它。 优化版本可能很难正确实现。 无论如何最终都会尝试，可以使用powershell版本来validation测试值的正确性，并对优化版本的速度进行基准测试。

Answer 5

大小不是sizeof(long)倍数这一事实是问题中最难的部分。 这可能导致大量的位移。

但是，如果您可以引入新的struct成员，则不必这样做：

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

偏移量会告诉您在数组开头要忽略多少位。

那你只需要做以下步骤：

1. 反向数组元素。
2. 交换每个元素的位。 在其他答案中有很多hacks，但是你的编译器也可能提供有用的function来用更少的指令（比如某些ARM内核上的RBIT指令）。
3. 计算新的起始偏移量。 这等于最后一个元素具有的未使用位。

Answer 6

我会把问题分成两部分。

首先，我会忽略这样一个事实，即使用的位数不是32的倍数。我会使用给定方法之一来交换整个数组。

伪代码：

 for half the longs in the array: take the first longword; take the last longword; swap the bits in the first longword swap the bits in the last longword; store the swapped first longword into the last location; store the swapped last longword into the first location; 

然后修复一个事实，即前几位（调用数字n ）实际上是longs末尾的垃圾位：

 for all of the longs in the array: split the value in the leftmost n bits and the rest; store the leftmost n bits into the righthand part of the previous word; shift the rest bits to the left over n positions (making the rightmost n bits zero); store them back; 

您可以尝试将其折叠成整个arrays中的一个传递。 像这样的东西：

 for half the longs in the array: take the first longword; take the last longword; swap the bits in the first longword swap the bits in the last longword; split both value in the leftmost n bits and the rest; for the new first longword: store the leftmost n bits into the righthand side of the previous word; store the remaining bits into the first longword, shifted left; for the new last longword: remember the leftmost n bits for the next iteration; store the remembered leftmost n bits, combined with the remaining bits, into the last longword; store the swapped first longword into the last location; store the swapped last longword into the first location; 

我从这里的边缘情况（第一个和最后一个长字）中抽象出来，你可能需要根据每个长字内部的位排序来反转移位方向。