[Cryptography] Exotic Operations in Primitive Construction

[John Tromp]

> > As another followup (and I'm not trying to turn this into a C forum), but
> > can anyone think of a way to flip an n-bit word around i.e. LSB becomes
> > MSB etc?
> >
>
> Generally as follows. For simplicity's sake I've removed the container
> type you need to store an arbitrary sized number. You should see the
> size of the type as a potential parameter.
>
> uint16_t reverse(uint16_t v) {
>         uint16_t r = 0;
>         for (int i = 0; i < 16; i++) {
>                 r |= (((1 << i) & v) >> i) << (15 - i);
>         }
>         return r;
> }

This can be done more efficiently in log_2(w) steps for w-bit wide values.
Hint: x = (x & 0xaaaa) >> 1 | (x & 0x5555) << 1; swaps adjacent bits.