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