с++: rapid actions with bits positions

Question

There is a task: There are 2 numbers:

src specifies numbers from 0 to 31 by setting the corresponding bit.
dst specifies the positions of the numbers set in src to be selected

For example:

src = 0b11010110 - numbers №1 = 1, №2 = 2, №3 = 4, №4 = 6, №5 = 7

mask = 0b00001010 - extract numbers №1, №3 from src

result = 0b01000100

Can you tell me how quickly you can do this? I wrote the code below, but maybe you can do a lot better?

int unzip_variant(const int src, const int mask)
{
    int unzipped = 0;

    int pos = 0;

    for (int index = 1; index <= с_size; index ++)
    {
        if (src & (1 << index))
        {
            pos += 1;

            if (mask & (1 << pos))
                unzipped |= (1 << index);
        }
    }

    return unzipped;
}

If you want to improve your code that is already working, you might want to move this to https://codereview.stackexchange.com/ — nada, May 13 '20 at 12:15
@nada, maybe we need a fundamentally different algorithm rather than improving the current one. — Zhihar, May 13 '20 at 12:30
Fundamentally different algorithms are on topic at codereview. — user58697, May 13 '20 at 16:50
The specification is unclear, the example makes no sense (it doesn't have `dst` and it's unclear why the result is what it is), and the code basically implements `src & mask` except it skips the first bit (which just looks like a bug). Please improve the question to make it clear what the function should do. — harold, May 14 '20 at 09:42
With a [ffs](https://en.wikipedia.org/wiki/Find_first_set)-function ([index of the rightmost 1-bit](https://stackoverflow.com/q/14997894/6770384)) you could reduce the number of loop iterations from `sizeof(int)*8` to `number of 1-bits in src with № <= index of leftmost 1-bit in mask`. However, I'm skeptical whether this will speed things up (unless you have hardware support for `ffs`). — Socowi, May 14 '20 at 14:32

olegarch · Accepted Answer · 2020-05-25T12:59:22.527

I hope, I correctly understand your problem, and wrote this solution:

// x: value, m: mask, for your dataset: unzip(0xd6, 0xa) -> 0x44
unsigned unzip(unsigned x, unsigned m) {
  unsigned bit, mm;
  for(mm = 0, bit = 1; bit <= x; bit <<= 1)
    if(bit & x)
      mm |= bit & m;
    else
      m <<= 1;
  return x & mm;
}

Possible useful modifications of if continue condition:

for(mm = 0, bit = 1; bit <= x && bit != 0; bit <<= 1)

bit != 0 - is useful, if sign bit (highest) of x is also contains data

score 0 · Answer 2 · answered Jun 05 '20 at 12:27

experimentally obtained the fastest code I couldn't get faster.

int unzip_variants(
    const int   numbers,
    const int   variants
)
{
    int unzipped_variants = 0;

    int pos = 0;

    for (int index = 1; index <= с_size; index++)
    {
        pos += (variants >> index) & 1;
        unzipped_variants |= (((variants >> index) & 1) *
                                ((numbers >> pos) & 1)) << index;
    }

    //  for (int variants_index = 1; variants_index <= с_size; variants_index++)
    //  {
    //      if (variants & (1 << variants_index))
    //      {
    //          pos += 1;
    //
    //          if (numbers & (1 << pos))
    //              unzipped_variants |= (1 << variants_index);
    //      }
    //  }

    return unzipped_variants;
}

с++: rapid actions with bits positions

2 Answers2