Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Reverse the order of bits in a bit array

Tags:

c

bitarray

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.

like image 341
Eques Avatar asked Nov 25 '15 07:11

Eques


People also ask

How do you reverse a bit?

Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution. This permutation can be applied to any sequence in linear time while performing only simple index calculations.

How do you reverse the bit of a number in Java?

The java. lang. Integer. reverse() method returns the value obtained by reversing the order of the bits in the two's complement binary representation of the specified int value.


2 Answers

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.

like image 166
Yves Daoust Avatar answered Sep 22 '22 16:09

Yves Daoust


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;
}
like image 41
AndreyS Scherbakov Avatar answered Sep 20 '22 16:09

AndreyS Scherbakov