bit manipulation - Mask and aggregate bits -

i'm trying efficiently execute following task:

input value: 01101011 mask:        00110010 mask result: --10--1- aggregated:  00000101 

i hope examples explains i'm trying achieve. what's best way in non-naive way?

this operation called compress_right or compress, , moderately terrible implement without hardware support. non-naive code hacker's delight "7–4 compress, or generalized extract" implement function is

unsigned compress(unsigned x, unsigned m) {     unsigned mk, mp, mv, t;     int i;     x = x & m;    // clear irrelevant bits.     mk = ~m << 1; // count 0's right.     (i = 0; < 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 move.         m = m ^ mv | (mv >> (1 << i)); // compress m.         t = x & mv;         x = x ^ t | (t >> (1 << i));   // compress x.         mk = mk & ~mp;     }     return x; } 

bmi2 (implemented in haswell , later) have instruction pext operation.

---

if mask constant (or not constant reused multiple times), relatively obvious optimization pre-calculating 5 values mv takes during loop. calculation of mv not depend on x, can calculated independantly, (the same algorithm above really)

mk = ~m << 1; (i = 0; < 5; i++) {     mp = mk ^ (mk << 1);     mp = mp ^ (mp << 2);     mp = mp ^ (mp << 4);     mp = mp ^ (mp << 8);     mp = mp ^ (mp << 16);     mv = mp & m;     mask[i] = mv;     m = m ^ mv | (mv >> (1 << i));     mk = mk & ~mp; } 

still looks complicated, here constant, can pre-computed (if compiler can't it, you can, running , pasting result code). "real part" of code, code has run @ runtime this:

x = x & m; t = x & mask[0]; x = x ^ t | (t >> 1); t = x & mask[1]; x = x ^ t | (t >> 2); t = x & mask[2]; x = x ^ t | (t >> 4); t = x & mask[3]; x = x ^ t | (t >> 8); t = x & mask[4]; x = x ^ t | (t >> 16); 

(this in hacker's delight, formatted little differently)

many cases can simpler again, example:

• if m = 0, result 0.
• if m = -1, result x.
• if m = 1, result x & 1.
• if m = ((1 << n) - 1) << k, result (x >> k) & m.
• if m = 0x80000000, result x >> 31.
• if m other power of two, result (x >> numberoftrailingzeros(m)) & 1
• if m alternating, "perfect unshuffle algorithm" can used.
• if m consists of few "groups", "bit group moving" algorithm can used (ie mask group, shift place (or shift first, mask second), or shifted groups together, though more sophisticated approaches exist), important case in practice.
• ...

for example, mask question fall in "bit group moving" case, code this:

return ((x >> 1) & 1) | ((x >> 3) & 6);