Reversing Bit for FFT in Python

I always found this Fast Fourier Transform (FFT) business a little foggy. Now what happened is that on my new Leopard distribution after the installation of Matplotlib I found that I had the fft function but not the ifft function… So in the end I took the legendary Numerical Recipes book and I started to convert the C++ version in python. Well, let me say that it wasn’t that trivial since the C++ version was based on vectors with intercalated real and imaginary parts which were messing up the understanding of the indexes in some of the for loops… In the end I managed. Here is the code for the function needed: you need a function to rearrange the input vector reversing position according their number in binary format (i.e. 0101 goes into 1010 and 0001 into 1000 etc.)… here is the code:

"""
This function serves as a base for the calculation of FFT. It simply
swaps vector elements just according to their position expressed in
binary digits. For example using a vector of lenght 16 (4 bits), the
vector element 4 = 0100 transforms into 0010 = 2 and 10 = 1010 goes
into 0101 = 5 and so on...
"""
def bitReverse(x):

	xn = 1.0*x
	N = int(len(xn))
	if N%2 != 0: raise ValueError, 'N is not power of 2'
	j = 0
	for i in range(0,N):
		if j>i:
			shelf = xn[j]
			xn[j] = xn[i]
			xn[i] = shelf
		m = N/2
		while (m >= 2 and j > m-1):
			j = j-m
			m = m >> 1
		j += m

	return xn