3

Given an interlaced bit sequence of:

ABABABABABABABAB

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

AAAAAAAABBBBBBBB
5
  • 1
    I'm not sure I follow your question. Are you having a byte sequence and you want to use bitwise operations on them, or you have a bit sequence and want to use bitwise operations on them?
    – Re Captcha
    Apr 10, 2014 at 10:09
  • Sorry, it's a bit sequence, so it would be a series of 16 bits interleaved that I want de-interleave (1010101010101010 to 1111111100000000) Apr 10, 2014 at 10:32
  • Obviously that example sequence is arbitrary, so could be any mix of 1's and 0's, but I need to move all the Odd positioned entries into one block, and all the Even position entries into another. Apr 10, 2014 at 10:38
  • 16 bits only and not 32 bits?
    – Re Captcha
    Apr 10, 2014 at 10:51
  • 1
    It's an entry in a Uint16Array, so I'm assuming 16? Apr 10, 2014 at 10:55

2 Answers 2

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.

1
  • This works great thanks. Just for the sake of completness, this is what I ended up with for my 16bit numbers (as per your instructions): t = (x ^ (x >> 1)) & 0x2222; x = x ^ t ^ (t << 1); t = (x ^ (x >> 2)) & 0x0C0C; x = x ^ t ^ (t << 2); t = (x ^ (x >> 4)) & 0x00F0; x = x ^ t ^ (t << 4); Apr 10, 2014 at 12:39
1

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.