Efficient endianness reversal for arbitrary number of bits

I have a list of length 2^n which is indexed with numbers up to 2^n-1, but the problem is that I would like to reorder the list with the bitwise reverse-endian indexing.

For example if n = 4, I want to swap indices 0001<->1000, 0010<->0100, 0011<->1100, and so on...

Solutions I have looked at so far seem to only reverse endianness of bytes (I am interested in bits), or relying on built-in functions that don't work on arbitrary number of bits.

The makeshift way I'm currently doing this (Python/C++) is to convert each index to a string, reverse the string and convert back to index, but this seems very inefficient. What would be a better way to do this?

Solution

Performing the bit-reversal permutation does not require actually bit-reversing any integers (that is a way to implement it of course, but not a great one). That's because the algorithm to do the actual permutation does not ask for arbitrary bit-reversed integers in no particular order. It would be OK to have this sequence (for n=4)

An other trick to generate that sequence uses that the i + 1 operation carries through the least significant set bits, making them all zero, and then it sets the least significant unset bit. Or in other words, it's like the operation "invert the bits starting at the LSB, but stop after inverting the first zero". That operation can be bit-reversed relatively easily, we just need to XOR by some mask of contiguous set bits, the length of which can be found by computing __builtin_ctz(i + 1) + 1 (the final +1 is to include the zero that changed to a one in the count). Then the mask itself can be found as N - (N >> maskLength) where N is the size of the array (a power of two, subtracting the shifted version of it sets all the bits starting at that lower position up to the higher position).

For example: (not tested)

for (uint32_t i = 0, rev = 0; i < N; ++i)
{
    if (i < rev)
        swap(X[i], X[rev]);
    int maskLen = __builtin_ctz(i + 1) + 1;
    rev ^= N - (N >> maskLen);
}

__builtin_ctz is for GCC and Clang, for MSVC you can use _BitScanForward (it works a bit differently).

There is a similar trick that uses the leading zero count of i ^ (i + 1).

By the way if this is being used as part of an FFT, you could consider using algorithms that don't need this, for example the Natural-Order Cooley-Tukey Algorithm, or the Stockham Auto-Sort Algorithm.

Actually reversing an arbitrary n-bit number can be done by first reversing it totally and then shifting it right by 32 - bits (or 64, if a 64bit reverse was performed). For every particular n there is also a corresponding special-case bit-manipulation trick, but then that n is baked into the code as a constant. Using a full reverse followed by shifting works for variable n. Some CPUs may have instructions that help with that, for example ARM (actually ARMv6T2 and above) has RBIT.