CODEWITHSUNDEEP
algorithmbit-manipulation
Expedito
Expedito

Reputation: 7795

Expand Right Bitwise Algorithm

Originally this post requested an inverse sheep-and-goats operation, but I realized that it was more than I really needed, so I edited the title, because I only need an expand-right algorithm, which is simpler. The example that I described below is still relevant.

Original Post:

I'm trying to figure out how to do either an inverse sheep-and-goats operation or, even better, an expand-right-flip.

According to Hacker's Delight, a sheeps-and-goats operation can be represented by:

SAG(x, m) = compress_left(x, m) | compress(x, ~m)

According to this site, the inverse can be found by:

INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw)

However, I can't find any code for the expand_left and expand_right functions. They are, of course, the inverse functions for compress, but compress is kind of hard to understand in itself.

Example:

To better explain what I'm looking for, consider a set of 8 bits like:

0000abcd

The variables a, b, c and d may be either ones or zeros. In addition, there is a mask which repositions the bits. So for example, if the mask were 01100101, the resulting bits would be repositioned as follows:

0ab00c0d

This can be done with an inverse sheeps-and-goats operation. However, according to this section of the site mentioned above, there is a more efficient way which he refers to as the expand-right-flip. Looking at his site, I was unable to figure out how that can be done.

Upvotes: 3

Views: 404

Answers (1)

user555045
user555045

Reputation: 64904

Here's the expand_right from Hacker's Delight, it just says expand but it's the right version.

unsigned expand(unsigned x, unsigned m) {
    unsigned m0, mk, mp, mv, t;
    unsigned array[5];
    int i;
    m0 = m;        // Save original mask.
    mk = ~m << 1;  // We will count 0's to right.
    for (i = 0; i < 5; i++) {
        mp = mk ^ (mk << 1);             // Parallel suffix.
        mp = mp ^ (mp << 2);
        mp = mp ^ (mp << 4);
        mp = mp ^ (mp << 8);
        mp = mp ^ (mp << 16);
        mv = mp & m;                     // Bits to move.
        array[i] = mv;
        m = (m ^ mv) | (mv >> (1 << i)); // Compress m.
        mk = mk & ~mp;
    }
    for (i = 4; i >= 0; i--) {
        mv = array[i];
        t = x << (1 << i);
        x = (x & ~mv) | (t & mv);
    }
    return x & m0;     // Clear out extraneous bits.
}

You can use expand_left(x, m) == expand_right(x >> (32 - popcnt(m)), m) to make the left version, but that's probably not the best way.

Upvotes: 2

Related Questions