Isolating bits and flattening them

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?

This sounds nasty. What's the actual problem that you're trying to solve? There must be an easier way. — Pete Becker, Aug 21 '17 at 19:03
For predefined bit masks you could generate the shifts at compile time with some TMP. — rustyx, Aug 21 '17 at 19:06
I read it 5 times, still can't understand what flattened bit means. What is the truth table for this operation? — SergeyA, Aug 21 '17 at 19:08
@PeteBecker I'm trying to decode operands embedded in opcodes, e.g. getting the values of `r` and `d` given the pattern `0000 11rd dddd rrrr`. — Brandon, Aug 21 '17 at 19:08
@SergeyA With the pattern `0000 11rd dddd rrrr` (where `r` and `d` are arbitrary bit values), applying a mask for `r` would give you `____ __r_ ____ rrrr`. I would like to then "flatten", or get rid of the useless bits (`_`) in between the remaining `r`s, leaving me with just a continuous number `000r rrrr`. — Brandon, Aug 21 '17 at 19:11
I am still not following. There are only 0 and 1 values in any given bitset, yet your example has 4 - 0, 1, r, and d. Can you please provide a real bitset example? — SergeyA, Aug 21 '17 at 19:15
I'd go with an ad hoc approach. You'll typically need a small handful of shifts and masks; not a big deal. The broad generic case that I thought you were describing originally is still nasty, but, luckily, you don't have that. — Pete Becker, Aug 21 '17 at 19:15
NO, there's no neat way of doing it. You can build a fairly simple function to flatten a bitset for you, or hardcode lots of shits and masks. — Malcolm McLean, Aug 21 '17 at 19:17
@SergeyA -- he wants to gather the **values** from the `r` bits into a register index. So think of the `r` bits as being numbered: `r4`, `r3`, `r2`, `r1`, `r0`, from left to right in the pattern. Compute the value as if those bits were all contiguous: `r4r3r2r1r0`. It's a common hardware thing, where the bits for different things are interleaved and you have to pick out the bits for one of the things. — Pete Becker, Aug 21 '17 at 19:18
In most of the assembly languages I have encountered, there are no "useless" bits and the bits depend on their positions. For example, if a register field is 101 (meaning register 5), you can't squish or flatten to 11 because 11 means register 3. This also applies to bit patterns in hardware devices. — Thomas Matthews, Aug 21 '17 at 19:24
See also [Bit twiddling hacks](https://graphics.stanford.edu/~seander/bithacks.html) — Thomas Matthews, Aug 21 '17 at 19:29
The only reason I was looking to move away from ad hoc bit shifts was to be able to make a listing of opcodes and their operand positions, such that I could parse using the that instead of hard-coding each individual operand's decoding. The idea behind this is that I could go both ways, i.e. encode and decode, without needing to hard-code the bitshifts twice (1 to read, 1 to write). Should there be no neat way to do this, I will likely stick to implementation **b)** and only store the masks in the table (I could see creating two lambda's and storing those a la **a)** but that sounds ugly) — Brandon, Aug 21 '17 at 19:38
so you want to pack the selected bits? That's called [parallel bits deposit in x86](https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#Parallel_bit_deposit_and_extract). [Portable efficient alternative to PDEP without using BMI2?](https://stackoverflow.com/q/38938911/995714), [Extracting bits with a single multiplication](https://stackoverflow.com/q/14547087/995714), [what is the most efficient way to pack left based on a mask?](https://stackoverflow.com/q/36932240/995714) — phuclv, Aug 22 '17 at 03:44

samgak · Answer 1 · 2017-08-22T03:27:45.247

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)

Isolating bits and flattening them

Problem

Tried solutions

Question

1 Answers1