Question

Given an interlaced bit sequence of:

ABABABABABABABAB

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

AAAAAAAABBBBBBBB
Was it helpful?

Solution

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.

OTHER TIPS

Check out this algorithm, if it's good for you:

function deinterlace(input) {
    var maskOdd = 1;
    var maskEven = 2;
    var result = 0;
    for (var i = 0; i < 8; i++) {
        result = result << 1;
        if(maskOdd & input) {
            result += 1;
        }
        maskOdd = maskOdd << 2;
    }

    for (var j = 0; j < 8; j++) {
        result = result << 1;
        if(maskEven & input) {
            result += 1;
            console.log(result);
        }
    }
    return result;
}

Working fiddle.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top