mix N bits with next N bits (e.g each 4bits) 00001111 -> 01010101

Question

As the title of this question tells I want to know the best way to mix blocks of bits within an integer (especially 64bit unsigned)

for example I have 8bit integer, where it's bits are 0000 1111 mix 4bits by 4 bits = 0101 0101

example 2: 0010 0110
0 1 1 0 right *0.0.1.0 left* = 00011100 mix 4bits by 4 bits = 0001 1100 Simple is, . places filled with bits of right block

What I am doing rightnow:

uint64_t mix32(uint64_t v) {
    uint64_t ret=0;
    int x=0;
    for(int i=0; i<32; i++) {
        setbit(ret, x, getbit(v, i));
        x++;
        setbit(ret, x, getbit(v, i+32));
        x++;
    }

    return ret;
}

where setbit is a macro that sets or clears the bit on certain position. What exactly I need is mix each 32bits with next 32bits mix each 16bits with next 16bits mix each 16bits with after next 16bits mix each 8bits with next 8bits etc... I hope I can do rest if one example of such bit operations is available. I have looked on google a lot, but ended up with tutorials which do not demonstrate such scenario.

Stay well.

Answer 1

What I would do is have a 16-element table that holds the result of expanding each nibble for the multiplex operation. Then just left-shift 1 as needed and bitwise-or the results together.

Answer 2

See Bit twiddling hacks at the Interleave bits section for a few solutions.

Answer 3

Found solution from bit tweeding hacks - although it was not good spending a lot time on this small operation. I am sure there must be many good ways doing this, but I needed solution that can keep me concentrated on my research, am sure it is worst way.

uint64_t mix32(uint64_t v, bool right_even=true) {
    unsigned uint32_t x;   // Interleave bits of x and y, so that all of the
    unsigned uint32_t y;   // bits of x are in the even positions and y in the odd;
    unsigned uint64_t z = 0; // z gets the resulting Morton Number.

    if(right_even)
        v = swap32(v); //swap 32bit blocks

    char *n = (char*)malloc(sizeof(v));
    memcpy(n, &v, sizeof(v));
    memcpy(&y, n, sizeof(y));
    memcpy(&x, n+sizeof(x), sizeof(x));

    for (int i = 0; i < sizeof(x) * 8; i++) // unroll for more speed...
       z |= (x & 1ULL << i) << i | (y & 1ULL << i) << (i + 1);

    return z;
}

stay well.

Answer 4

unsigned __int64 mix32(unsigned __int64 v, bool right_even=true) {
    unsigned __int64 z = 0; 

    if(right_even)
        v = swap32(v);

    unsigned __int32 x = (v&0xffffffffUL);
    unsigned __int32 y = (v&0xffffffffUL)>>32;

    for (int i = 0; i < sizeof(x) * 8; i++) 
       z |= (x & 1ULL << i) << i | (y & 1ULL << i) << (i + 1);

    return z;
}