De-interlace bytes

Question

Given an interlaced bit sequence of:

ABABABABABABABAB

What javascript bitwise operation can I use to convert it to be in the sequence:

AAAAAAAABBBBBBBB

Answer 1

That's known as an unshuffle (see also Hacker's Delight 7.2, shuffling bits).

The algorithm given in Hacker's Delight is:

t = (x ^ (x >> 1)) & 0x22222222;  x = x ^ t ^ (t << 1); 
t = (x ^ (x >> 2)) & 0x0C0C0C0C;  x = x ^ t ^ (t << 2); 
t = (x ^ (x >> 4)) & 0x00F000F0;  x = x ^ t ^ (t << 4); 
t = (x ^ (x >> 8)) & 0x0000FF00;  x = x ^ t ^ (t << 8); 

Those right shifts can be either logical or arithmetic, the AND with the mask ensures that bits affected by that difference do no appear in t anyway.

This is for 32bit numbers, for 16 bit numbers you can chop off the left half of every mask and skip the last step.

This is a sequence of delta swaps, see The Art of Computer Programming volume 4A, Bitwise tricks and techniques, bitswapping.