Efficient Vector Bit-Data "Rotation" / "Rearrangement" in Memory [e.g. in Python, Numpy]
Question: How does one efficiently convert from an 8 element long array of e.g. uint8s
into a its "rotated" counterpart, were e.g. the original 8bits of the first
element are spread across all vector elements as the MSB, and the second last
element spread across the second MSB, and so on: Working and slow example:

    
    
    import numpy as np
    
    original = np.random.randint(0, 255, 8).astypye(np.uint8) # some random example vector
    [np.binary_repr(i, width=8) for i in original]            # original data
    =>['01111111',
       '00100111',
       '01110111',
       '00100010',
       '00111101',
       '10010000',
       '10000100',
       '10101000']
    
    rotated = np.packbits(np.unpackbits(original).reshape(-1,8).T) # <= SLOW ROTATION
    [np.binary_repr(i, width=8) for i in rotated]                  # this is should be the result
    =>['00000111',                                                 # what where rows originally
       '10100000',                                                 # are now columns
       '11111001',
       '10101100',
       '10001001',
       '11101010',
       '11110000',
       '11101000']
    

So in the end, I want to reorder the layout how BITS are "filed" into the RAM.
As you can see I got a working example in Numpy, it is not super slow (here ~
21 µs), however I would like to do this excercise with data structures in the
order of ~2k * 1 mio bits. Therefore the usage of the numpy or C bool dtype is
to wasteful (factor 8 overhead).

Any C bit shuffling magic or SSE instructions or general answers are welcome!


Answer: I suggest looking at the source provided
[here](http://programming.sirrida.de/calcperm.php)

In particular, calcperm.cpp. This is a simple bit permutation problem.

