Best way to extract ODD digits from a binary number

Question

Given a 64 bit number, I need to extract every other bit from it, and convert it into a number:

decimal:  357
binary:   0000 0001 0110 0101
odd bits:  0 0  0 1  1 0  1 1
decimal:  27

Any idea of a good algorithmic way to do it? And no, not HW, this is for a real world use :)

Answer 1

I would go with performing Arithmetic Right Shift(till the length of the binary number) two at a time. This >> used in my logic is for arithmetic shift.

(Note: In C language, right shifts may or may not be arithmetic!)

Like,

int count=0;
bit=extractLastbit(binary_representation_of_the_number);

while(count!=binaryLength){
  // binaryLength is the length of the binary_representation_of_the_number
  binary_representation_of_the_number=binary_representation_of_the_number>>2;

  bit.appendLeft(extractLastbit(binary_representation_of_the_number);
  count=count+2;
}

where,

extractLastBit() extracts the LSB of the binary number; appendLeft() performs shifting the newly extracted bit to the left of the older bit(s).

Answer 2

See How to de-interleave bits (UnMortonizing?).

x = x& 0x5555555555555555; //restrict to odd bits.
x = (x | (x >> 1)) & 0x3333333333333333;
x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff0000ffff;
x = (x | (x >>16)) & 0x00000000ffffffff;

Answer 3

Create a table of 256 entries to look up say each byte. The value of an entry in the table will be the thing converted to a number. Then paste the 4 bytes together with shifts to come up with the final number.

Here is an example scaling things down so you get the idea. The lookup part using 4 bits instead of 8:

0000 = 00
0001 = 01
0010 = 00
0011 = 01
0100 = 10
0101 = 11
...

Looking up say 01010010. Break up into 0101 and 0010. Look those up we get 11, and 00 and paste together: 1100

With a table of 256, you'll need 8 lookups with the corresponding pasting. If you have memory for 2**16 entries then you need only go with four lookups and the pasting is proportionally less too.

The table doesn't have to an even power of two. For example with 1024 entries (2**10) there are 7 lookups. There is just an economy when the table exponent happens to be a power of two (2, 4, 8, 16 or 32).

Answer 4

Here's what I eventually came up with - every ODD bit going from/to X value, and every EVEN bit - from/to Y. I had to write it in JavaScript.

function xyToIndex(x, y) {
    // Convert x,y into a single integer with alternating bits
    var mult = 1, result = 0;
    while (x || y) {
        result += (mult * (x % 2));
        x = Math.floor(x / 2);
        mult *= 2;
        result += (mult * (y % 2));
        y = Math.floor(y / 2);
        mult *= 2;
    }
    return result;
}

function indexToXY(index) {
    // Convert a single integer into the x,y coordinates
    // Given a 64bit integer, extract every odd/even bit into two 32bit values
    var x = 0, y = 0, mult = 1;
    while (index) {
        x += mult * (index % 2);
        index = Math.floor(index / 2);
        y += mult * (index % 2);
        index = Math.floor(index / 2);
        mult *= 2;
    }
    return [x, y];
}