Bit-reversed counting

[Joseph Nathan Hall]

All the discussion about bit counting has reminded me of an analytically
unrelated problem that still sounds similar.  Bit-reversed counters are used
in FFT algorithms (and probably other things I don't know about).  I
have occasionally wondered what interesting ways there of implementing
bit-reversed counting . . .

An example of bit-reversed counting for your edification:

	Normal			Bit-reversed

	0001	1		1000	8
	0010	2		0100	4
	0011	3		1100	12
	0100	4		0010	2
	0101	5		1010	10
	...etc.

In a similar vein, what interesting bit-reversal algorithms are there
(distinct from the problem of COUNTING bit-reversed)?

I would consider algorithms that don't use tables (or, better, use very 
small or tricky tables) much more interesting than the obvious brute-force
approaches.

I will post a summary of anything worthwhile that's mailed to me, but
if you have a method of general interest I'd suggest you go ahead and post
it yourself (succintly).


-- 
v   v sssss|| joseph hall                      || 201-1D Hampton Lee Court
 v v s   s || jnh at ece-csc.ncsu.edu (Internet)  || Cary, NC  27511
  v   sss  || the opinions expressed herein are not necessarily those of my
-----------|| employer, north carolina state university . . . . . . . . . . .