benchmark/fourier/parallel/pi/xeonphi/openmp/fourier-parallel-pi-xeonphi-openmp.c
uint32_t bit_reverse(uint32_t x, uint32_t m){
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));

  return ((x >> 16) | (x << 16)) >> (32-m);
}
// This function bit-reverses the given index (represented as a m-bit binary 
// number), and returns the resulting value as an integer.
// 
// This is used in the final step of the FFT: due to the recursive nature of
// the factorization, the butterfly's outputs are always in bit-reversed order
// (when represented as log(N)-bit numbers, where N is the input size). So for
// instance for a butterfly of size 8, the 1st output of the butterfly actually
// maps to the 1 -> 001 -> 100 -> 4th output of the array; while the 3rd output
// of the butterfly maps to the 3 -> 011 -> 110 -> 6th output of the array; and
// so forth.
//
// The algorithm below comes from:
//
//  Dietz, H. (2002) The Aggregate Magic Algorithms. University of Kentucky.
//   http://aggregate.org/MAGIC/#Bit%20Reversal
//
// which decomposes the (m m-1 ... 1) permutation into log m cycles: first swap
// all adjacent bits, then swap every two bits, and so forth.
// 
// Note, however, Dietz' particular algorithm is hard-wired to m=32-bits only:
// so in the example above, 3 is not mapped to 110 but to 1100 0000 0000 0000 
// 0000 0000 0000 0000; so, at the end, I just right-shift the result by 32-m 
// bits to obtain the desired value (in this case, 110 -> 6).
// 
//   x:                      Index to bit-reverse.
//   m:                      How many bits to use when representing the index.
//
//   returns:                Bit-reversed integer value of x, when represented
//                           as a m-bit binary number.
// 
This function bit-reverses the given index (represented as a m-bit binary
number), and returns the resulting value as an integer.

This is used in the final step of the FFT: due to the recursive nature of
the factorization, the butterfly's outputs are always in bit-reversed order
(when represented as log(N)-bit numbers, where N is the input size).

The algorithm below comes from.

Dietz, H. (2002) The Aggregate Magic Algorithms. University of Kentucky.

which decomposes the (m m-1 ... 1) permutation into log m cycles: first swap
all adjacent bits, then swap every two bits, and so forth.



Index to bit-reverse.
m:                      How many bits to use when representing the index.

Bit-reversed integer value of x, when represented
as a m-bit binary number.
This function bit - reverses the given index ( represented as a m - bit binary number ) and returns the resulting value as an integer . This is used in the final step of the FFT : due to the recursive nature of the factorization the butterfly ' s outputs are always in bit - reversed order ( when represented as log ( N ) - bit numbers where N is the input size ) . The algorithm below comes from . Dietz H . ( 2002 ) The Aggregate Magic Algorithms . University of Kentucky . which decomposes the ( m m - 1 ... 1 ) permutation into log m cycles : first swap all adjacent bits then swap every two bits and so forth . Index to bit - reverse . m : How many bits to use when representing the index . Bit - reversed integer value of x when represented as a m - bit binary number .
uint32_t bit_reverse(uint32_t x, uint32_t m){
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
  return ((x >> 16) | (x << 16)) >> (32-m);
}
uint32_t bit_reverse ( uint32_t x , uint32_t m ) { x = ( ( ( x & 0xaaaaaaaa ) >> 1 ) | ( ( x & 0x55555555 ) << 1 ) ) ; x = ( ( ( x & 0xcccccccc ) >> 2 ) | ( ( x & 0x33333333 ) << 2 ) ) ; x = ( ( ( x & 0xf0f0f0f0 ) >> 4 ) | ( ( x & 0x0f0f0f0f ) << 4 ) ) ; x = ( ( ( x & 0xff00ff00 ) >> 8 ) | ( ( x & 0x00ff00ff ) << 8 ) ) ; return ( ( x >> 16 ) | ( x << 16 ) ) >> ( 32 - m ) ; }
This function bit-reverses the given index (represented as a m-bit binary
number), and returns the resulting value as an integer.
This function bit - reverses the given index ( represented as a m - bit binary number ) and returns the resulting value as an integer .