Bit format conversion using bit-manipulation operators

Question

I have a bit conversion problem that I am a bit struggling with. A bit of background... working on some computation biology problems and so need to to be supper fast (dealing with massive data sets). Basically I have the following bit representation of SNP's and I want to write some mask/and/xor/etc. operations so that I can quickly convert from one representation to the next:

00 -> 100

01 -> 010

11 -> 001

So for example 00010111 should convert to 100010010001. I am storing the bits in a rather large java.util.BitSet and would idealy like to be able to convert them to the new format just using bit operators.

Any help would be very welcome!

Answer 1

I'd use a lookup table. Grab 16 bits at a time and look them up in a 64K table with 24 bit entries.

int[] table = new int[65536];
table[0] = 0b100100100100100100100100;
table[1] = 0b100100100100100100100010;
...
table[65535] = 0b001001001001001001001001;
BitSet output = new BitSet();
for (int i = 0; i < length; i += 16) {
    int x = (input.get(i) ? 1 : 0)
          + (input.get(i+1) ? 2 : 0)
          ...
          + (input.get(i+15) ? 32768 : 0);
    int y = table[x];
    output.set(i/16*24, (y & 1) != 0);
    output.set(i/16*24 + 1, ((y>>1) & 1) != 0);
    ...
    output.set(i/16*24 + 23, ((y>>23) & 1) != 0);
}