On 1/23/24 23:13, Jan Schultke wrote:
> Can you elaborate on this? The article you've linked makes no mention
> of an operation like next_bit_permutation().
>
> All the linked references talk about bit-reversal, which is much
> different from next_bit_permutation().

I just realized that next_bit_permutation() does something different
from what I expected.

The confusion was introduced by the FFT motivation. While reverse_bits()
could be used for the bit-reversed permutation required by FFT, the
method is slow and seldomly used in practice. A faster method is to use
a different function that iterates over the bit-reversed numbers. See
for instance "Matters Computational" [1] where this function is called
revbin_upd() and the permutation is called revbin_permutation().

In summary, I do not believe FFT is a good motivation for reverse_bits()
and I have no idea what the use-cases for next_bit_permutation() are.

[1] https://www.jjj.de/fxt/