Fast permutation of bits in C#

Question

I'm implementing Charikar's fast search on a locality sensitive hash and I'm looking for a fast method of permuting bits (the kind of thing that can be done in one operation in MMIX) in C#.

The requirements are:

• Always less than 64 bits, so representation can be a long integer
• Randomly generate a permutation (this can be slow as it's only done once). I'll probably use a Knuth shuffle.
• Use the generated permutation many times, so this needs to be fast

I know Knuth goes into this in detail but I was wondering if there was any .NET/C# specific solution.

EDIT: I'm using .NET version 3.5.

Answer 1

Since C# doesn't provide any bit-manipulation instructions that Knuth didn't have in C, no, there's no .NET/C#-specific solution.

At the same time, .NET does offer dynamic compilation which will help you repeatedly perform the shuffle efficiently.

What version of .NET? The easiest approach will probably be to use Knuth's algorithm and encode the resulting operations in an Expression<Func<ulong, ulong>>, then compile the result as a Func<long, long> delegate.