Bit interleaving

[Joachim Durchholz]

Hi all,

I need to bit-interleave large integers.

A typical example would be four integers aaa, bbb, ccc, and ddd, with an 
interleaved result of abcdabcdabcdabcd (each letter stands for a single 
bit).
Typical integer size would be about 80 bits.
This is a mass application: there are *lots* of tuples to be interleaved.

I have taken a look at GMP, and while it seems easy enough to extract 
the bits and set them in the result, I'm thinking about optimization 
opportunities.
The question being, of course: is it worth the trouble?

I see two angles of attack:
1) Write C routines that do the interleaving directly on the 
representation level. Downside: constant maintenance overhead for 
keeping in sync with GMP updates. Advantage: seems to be fastest.
2) Construct the result integer object first, making sure that it is 
large enough to take up the result value, so there will be no 
unnecessary reallocations. Might be easy to do, too, simply by starting 
with the most significant bit.

Comments? Advice?

Regards,
Jo