[Cryptography] Exotic Operations in Primitive Construction

[Christian Huitema]

On 10/3/2020 9:14 AM, John Tromp wrote:
>>> 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.

"Reverse a bit chain" is a classic interview question for junior
software developers. The answer has better be O(logN), as Jerry and John
hinted.

-- Christian Huitema