reverse bit of a vector

[nurulhudaismail]

Hello,

If I have a vector of complex<double>s[4][1] = {
{ {1,0}},
{ {3,0}},
{ {6,0}},
{ {2,0}},
};

as my input. How can I do a reverse bit of each of the entries of s?

My problem is, I have this code, but I don't know to set s[4][1] as my input.Can anyone help me, please? Thank you.

unsigned int m = (unsigned int)log2(n);
	for (unsigned int a = 0; a < n; a++)
	{
		unsigned int b = a;
		//Reverse  bits
		b = (((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1));
		b = (((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2));
		b = (((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4));
		b = (((b & 0xff00ff00) >> 1) | ((b & 0x00ff00ff) << 8));
		b = ((b >> 16) | (b << 16)) >> (32 - m);
		if (b > a)
		{
			complex<double> t = s[a];
			s[a] = s[b];
			s[b] = t;

		}
	}

[jonnin]

without me having to unravel your mystery code, can you explain exactly what you want to do? Reverse bits ... 0001 -> 1000 or 0001 -> 1110 ??

you can reverse something bytewise with hton* type tools and then do whatever at the byte level. The cpu also probably has asm instructions that can do some of this kind of thing in 1 operation that c++ can't quite manage, if you don't need it portable.

[Duthomhas]

You are trying to do something unkosher, though if you are sure you are deploying on a i386+ processor and using only IEEE double precision (which you can configure with Windows compilers, though these days it is a whole new can of worms than it was with the x87 model — FP operations are very different now), then you can, in fact, make some bitwise guarantees.

Either way, you are also doing something senseless. A floating point is not just an integer, and manipulating its bits is more complicated than messing with an integer’s bits. Bit reversal (of any kind) is useful for some integer operations, but only in very rare contexts for floating point values.

The algorithm you are using (and goofing up at the end of line 10) is called
“Reverse an N-bit quantity in parallel in 5 * lg(N) operations”, and can be found explained here: https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

As written, it modifies a 32-bit value, which is a 32/8 = 4 byte object. Doubles are 8 bytes, unless they get on the FPU stack, when they are 10, or if they are managed via MMX instructions or the like, where you are SOL.

So... what exactly are you trying to accomplish?

[mbozzi]

Bit reversal is used in the base-2 Cooley-Tukey FFT algorithm, and that's the only time I've ever seen it used. If you are indeed trying to implement a FFT, I suggest giving up and using a library like libfftw3 instead:
http://fftw.org/

[nurulhudaismail]

Basically, I would like to do Radix2 Fast Fourier Transform. I want to convert a vector that I get from my calculation, let say s[n][1] = w[n][n]*x[n][1] to S[k][1] using Cooley-Tukey method and the size of n could be very large. The code above is used to do a reverse bit so that I can rearrange my input of the FFT from (000-->001-->010-->011-->100-->101-->110-->111) to be (000--->100-->010-->110-->001-->101-->011-->111). My problem is, how I am going to complete this code using my input vector?

I know there is a library in C++, however, my intention is to run this code for virtual hardware (FPGA). That is why, I don't have any plan to use the library.

Thank you.

[jonnin]

you can accomplish that reversal on a block of bytes with a pure rotation, which again, can be done on most chips with a single assembly command. that is the fastest way if you are in a hurry.
slightly slower but no big deal is a lookup table for all 256 possible bytes.
eg table[100] = 001; //of course we don't use binary in code, but you get the idea
use a pointer...
double d = 1234.56;
unsigned char* cp = (unsigned char*)&d;
cp[0] = tbl[cp[0]]; //you can loop this or leave it unrolled.
cp[1] = tbl[cp[1]];
...
cp[7] = tbl[cp[7]];

[mbozzi]

You can accomplish that reversal on a block of bytes with a pure rotation

No, a rotation isn't sufficient (there's a counter example in a following paragraph).

A lookup table would be great, but in this case it's not merely single bytes that need to be bit-reversed, but rather indices into an array with an arbitrary power-of-two size 2^n.

Reverse binary indexing maps any such valid array index into another valid array index.
For example with n = 6, the operation maps the array index 0b0000 ... 0010 1011 into 0b0000 ... 0011 0101 - treating the original LSB as the new MSB of a 6-bit number and vice versa. That's not doable with a plain rotation, even when followed with a bitshift.

OP already has the bit reversal algorithm from that Stanford page. It looks correct to me. The bitshift on line 10 ensures that the the index refers to an element in-bounds of the array.

There's no floating point bitmath going on.

More info about the operation:
https://en.wikipedia.org/wiki/Bit-reversal_permutation

[mbozzi]

#include <stdio.h>
#include <inttypes.h>
#include <assert.h>

inline uint32_t reverse_bits(uint32_t b) 
{
  b = (((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1));
  b = (((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2));
  b = (((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4));
  b = (((b & 0xff00ff00) >> 1) | ((b & 0x00ff00ff) << 8));
  return ((b >> 16) | (b << 16));
}

inline uint32_t reverse_binary_index(uint32_t idx, uint32_t index_bit)
{ return reverse_bits(idx) >> (32 - index_bit); }

// array indices are 11 bits long.  2^11 = 2048
uint32_t const idx_bit = 11; 
uint32_t const idx_max = (1 << idx_bit) - 1;

int main()
{
  for (uint32_t idx = 0; scanf("%"SCNu32, &idx) == 1; )
  {
    assert(idx <= idx_max);
        
    char const* fmt 
      = "reverse_binary_index(0x%08"PRIx32", %"PRIu32") = 0x%08"PRIx32"\n";
    printf(fmt, idx, idx_bit, reverse_binary_index(idx, idx_bit));
  }
}

http://coliru.stacked-crooked.com/a/78967a59d878e641

See also:
https://pdfs.semanticscholar.org/c824/fdb7b698a4cab39d4d47738634463fc82b27.pdf

[jonnin]

ah, I see. I am not familiar enough with this, and was trying to go off just what was stated here.

[Duthomhas]

I'm still not sure if OP is trying to reverse doubles or if he has some hints in there somewhere