cbit-manipulationbit

Grouping bits based on binary mask


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.


Solution

  • 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.