Radix 4 reordering function I have a bit reordering function for a radix 4 algorithm which takes around 600 000 cycles to do its job for 4096 elements of floats (real and imaginary parts):

void bit_r4_reorder(float* x, float* y, int N)// N = 4096
{
  int bits = 0;
  int i, j, k;
  float tempr, tempi;

  for (i = 0; i &lt; MAXPOW; i++)//MAXPOW = 24
      if (pow_2[i] == N)
          bits = i;

  for (i = 0; i &lt; N; i++)
  {
      j = 0;
      for (k = 0; k &lt; bits; k += 2)
      {
         if (i &amp; pow_2[k])     j += pow_2[bits - k - 2];
         if (i &amp; pow_2[k + 1]) j += pow_2[bits - k - 1];
      }

  if (j &gt; i)
  {
    tempr = x[i];
    tempi = y[i];
    x[i] = x[j];
    y[i] = y[j];
    x[j] = tempr;
    y[j] = tempi;
  }
 }
}


I've counted the cycles for the different parts of this function and it turns to be (maybe pretty obvious) that the last for() loop containing the swap part is what takes the most part of cycles.

Can you look at this code and give me some hints or suggestion on how I can optimize the code (if it is even possible)?
First of all, my apologies. I completely misread your code.

Ultimately the goal is to reverse bit pairs. The task is very similar to reversing the bits (this discussion is really inspiring), and the approach should be along the same lines.

For example, the first solution can be adopted along the lines of (sorry for sloppy coding):

unsigned int radix4_reverse(unsigned int index)
{
    x = (((x &amp; 0xcccccccc) &gt;&gt; 2) | ((x &amp; 0x33333333) &lt;&lt; 2));
    x = (((x &amp; 0xf0f0f0f0) &gt;&gt; 4) | ((x &amp; 0x0f0f0f0f) &lt;&lt; 4));
    x = (((x &amp; 0xff00ff00) &gt;&gt; 8) | ((x &amp; 0x00ff00ff) &lt;&lt; 8));
    x = (x &gt;&gt; 16) | (x &lt;&lt; 16));
    return x &gt;&gt; (32 - bits);
}


(notice that the 0xaaaaaaaa/0x55555555 line is omitted for it will swap bits within a pair).

Regarding your code,


ifs inside the loop are serious performance killers
1 &lt;&lt; k is preferable to pow_2[k]. The compiler has better chances to optimize sequential shifts than sequential memory fetches. Besides, it relaxes the memory consumption.
You should operate on bit pairs (e.g. i &amp; (0x03 &lt;&lt; k) rather than individual bits.
| is cleaner than + (IMnsHO).
I recommend to pass bits instead of N.