Reverse the order of bits in a bit array

Question

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:

• 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, pseudocode, algo description etc. -- anything better than bruteforce ("bit by bit") approach is welcome.

Answer 1

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

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.

Example:

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.

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

Answer 2

I like the idea of lookup table. Still it's also a typical task for log(n) group bit tricks that may be very fast. Like:

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;
}

The underlying idea is that when we aim to reverse the order of some sequence we may swap the head and tail halves of this sequence and then separately reverse each of halves (which is done here by applying the same procedure recursively to each half).

Here is a more portable version supporting unsigned long widths of 4,8,16 or 32 bytes.

#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;
}