Grouping bits based on binary mask [duplicate]

Question

I am looking for an algorithm to group bits from byte A based on mask (or tap) from B, on byte C, starting from least-significant. By way of example, the mask/tap (B) has bits 1,3,4 set to 1, which tells us to extract bits 1,3,4 from byte A and group them incrementally, starting from the right, on byte C.

uint8_t A = 00110101
uint8_t B = 00011010
uint8_t C = 00000100

I only picked uint8_t for this example - in practice, the source byte, mask, and target could have any lenght.

Answer 1

Brian Kernighan's way:

uint8_t group(uint8_t A, uint8_t B) {
    uint8_t C = 0;
    uint8_t M = 1;
    uint8_t nextB;
    while (B) {
        nextB = B & B - 1;
        if (A & (B ^ nextB)) C |= M;
        M <<= 1;
        B = nextB;
    }
    return C;
}

int main() {
    uint8_t A = 0b00110101;
    uint8_t B = 0b00011010;
    uint8_t С = group(A, B);
    // ...
}

At each iteration, the lowest set bit of B mask is reset. The new value is written to nextB. The B ^ nextB operation allows us to determine the bit that has just been reset. The M variable contains the current bit to pack into result.

---

Without if statement (branchless):

uint8_t group(uint8_t A, uint8_t B) {
    uint8_t C = 0;
    uint8_t M = 1;
    uint8_t nextB, cond;
    while (B) {
        nextB = B & B - 1;
        cond = A & (B ^ nextB);
        C |= M & -(cond != 0);
        M <<= 1;
        B = nextB;
    }
    return C;
}

The -(cond != 0) expression returns the value where all the bits are set if cond contains at least one set bit. With it, we can reset M & -(cond != 0) mask when no bit setting is required. Which saves us from branching.