Isolating bits and flattening them [duplicate]

Question

Problem

Suppose I have a bit mask mask and an input n, such as

mask = 0x10f3 (0001 0000 1111 0011)
n    = 0xda4d (1101 1010 0100 1101)

I want to 1) isolate the masked bits (remove bits from n not in mask)

masked_n = 0x10f3 & 0xda4d = 0x1041 (0001 0000 0100 0001)

and 2) "flatten" them (get rid of the zero bits in mask and apply those same shifts to masked_n)?

flattened_mask = 0x007f (0000 0000 0111 1111)

bits to discard         (___1 ____ 0100 __01)
first shift             (  __ _1__ __01 0001)
second shift            (       __ _101 0001)
result         = 0x0051 (0000 0000 0101 0001)

Tried solutions

a) For this case, one could craft an ad hoc series of bit shifts:

result = (n & 0b10) | (n & 0b11110000) >> 2 | (n & 0b1000000000000) >> 6

b) More generically, one could also iterate over each bit of mask and calculate result one bit at a time.

for (auto i = 0, pos = 0; i < 16; i++) {
    if (mask & (1<<i)) {
        if (n & (1<<i)) {
            result |= (1<<pos);
        }
        pos++;
    }
}

Question

Is there a more efficient way of doing this generically, or at the very least, ad hoc but with a fixed number of operations regardless of bit placement?

Answer 1

A more efficient generic approach would be to loop over the bits but only process the number of bits that are in the mask, removing the if (mask & (1<<i)) test from your loop and looping only 7 times instead of 16 for your example mask. In each iteration of the loop find the rightmost bit of the mask, test it with n, set the corresponding bit in the result and then remove it from the mask.

int mask = 0x10f3;
int n = 0xda4d;

int result = 0;
int m = mask, pos = 1;
while(m != 0)
{
    // find rightmost bit in m:
    int bit = m & -m;
    if (n & bit)
        result |= pos;
    pos <<= 1;
    m &= ~bit; // remove the rightmost bit from m
}
printf("%04x %04x %04x\n", mask, n, result);

Output:

10f3 da4d 0051

Or, perhaps less readably but without the bit temp variable:

if (n & -m & m)
    result |= pos;
pos <<= 1;
m &= m-1;

How does it work? First, consider why m &= m-1 clears the rightmost (least significant) set bit. Your (non-zero) mask m is going to be made up of a certain number of bits, then a 1 in the least significant set place, then zero or more 0s:

e.g:

xxxxxxxxxxxx1000

Subtracting 1 gives:

xxxxxxxxxxxx0111

So all the bits higher than the least significant set bit will be unchanged (so ANDing them together leaves them unchanged), the least significant set bit changes from a 1 to a 0, and the less significant bits were all 0s beforehand so ANDing them with all 1s leaves them unchanged. Net result: least significant set bit is cleared and the rest of the word stays the same.

To understand why m & -m gives the least significant set bit, combine the above with the knowledge that in 2s complement, -x = ~(x-1)