c - Performing bit level permutations on a quadword -

c - Performing bit level permutations on a quadword -

i'm looking fastest possible way permutate bits in 64 bit integer.

given table called "array" corresponding permutations array, meaning has size of 64 , filled unique numbers (i.e. no repetition) ranging 0 63, corresponding bit positions in 64 bit integer, can permutate bits way

bit = getbitatpos(integer_, array[i]); setbitatpos(integer_, array[i], getbitatpos(integer_, i)); setbitatpos(integer_, i, bit); (by looping 0 63) getbitatpos beingness getbitatpos(integer_, pos) { homecoming (integer >>) pos & 1 }

setbitatpos founded on same principle (i.e. using c operators), under form setbitatpos(integer, position, bool_bit_value)

i looking faster way, if possible, perform task. i'm open solution, including inline assembly if necessary. have difficulty figure improve way this, thought i'd ask.

i'd perform such task hide info in 64 bit generated integer (where 4 first bit can reveal informations). it's bit improve xor mask imo (unless miss something), if tries find correlation. permits inverse operation not lose precious bits...

however find operation bit costly...

thanks

since permutation constant, should able come improve way moving bits 1 1 (if you're ok publishing secret permutation, can have go @ it). simplest improvement moving bits have same distance (that can modular distance because can utilize rotates) between them in input , output @ same time. methods if there few such groups.

if didn't work out you'd hoped, see if can utilize bit_permute_steps move or of bits. see rest of site more ideas.

if can utilize pdep , pext, can move bits in groups distance between bits can arbitrarily alter (but order can not). is, afaik, unknown how fast though (and they're not available yet).

the best method going combination of these , other tricks mentioned in other answers.

there many possibilities explore them all, really, you're not going find best way permutation, using these ideas (and others posted) can doubtlessly find improve you're using.

pdep , pext have been available while performance known, @ 3 cycle latency , 1/cycle throughput they're faster other useful permutation primitives (except trivial ones).

c algorithm bit-manipulation