Isolating and flattening bits

Question

Problem

Suppose I have a bit mask mask and input n , e.g.

 mask = 0x10f3 (0001 0000 1111 0011) n = 0xda4d (1101 1010 0100 1101) 

I want 1) isolate masked bits (remove bits from n not in mask )

 masked_n = 0x10f3 & 0xda4d = 0x1041 (0001 0000 0100 0001) 

and 2) "smooth" them (get rid of the zero bits in mask and apply the same shifts to masked_n )?

 flattened_mask = 0x007f (0000 0000 0111 1111) bits to discard (___1 ____ 0100 __01) first shift ( __ _1__ __01 0001) second shift ( __ _101 0001) result = 0x0051 (0000 0000 0101 0001) 

Trial solutions

a) For this case, you can create a special series of bit shifts:

 result = (n & 0b10) | (n & 0b11110000) >> 2 | (n & 0b1000000000000) >> 6 

b) In the general case, you can also iterate over each bit of mask and calculate the result one bit at a time.

 for (auto i = 0, pos = 0; i < 16; i++) { if (mask & (1<<i)) { if (n & (1<<i)) { result |= (1<<pos); } pos++; } } 

Question

Is there a more efficient way to do this as a whole, or at least ad hoc, but with a fixed number of operations, regardless of bit allocation?

Answer 1

A more efficient general approach would be to iterate over the bits, but only process the number of bits in the mask, removing the if (mask & (1<<i)) test from your loop and looping only 7 times instead of 16 for your example mask. At each iteration of the loop, find the rightmost bit of the mask , check it with n, set the corresponding bit to the result, and then remove it from the mask.

 int mask = 0x10f3; int n = 0xda4d; int result = 0; int m = mask, pos = 1; while(m != 0) { // find rightmost bit in m: int bit = m & -m; if (n & bit) result |= pos; pos <<= 1; m &= ~bit; // remove the rightmost bit from m } printf("%04x %04x %04x\n", mask, n, result); 

Output:

 10f3 da4d 0051 

Or perhaps less readable, but without the bit temp variable:

 if (n & -m & m) result |= pos; pos <<= 1; m &= m-1; 

How it works? First, think about why m &= m-1 clears the rightmost (least significant) bit of the set. Your (non-zero) mask m will consist of a certain number of bits, and then 1 in the least significant place, then zero or more 0s:

eg:

 xxxxxxxxxxxx1000 

Subtraction 1 gives:

 xxxxxxxxxxxx0111 

Thus, all bits exceeding the least significant bit will be unchanged (therefore, combining them does not leave them unchanged), the least significant set bit changes from 1 to 0, and the least significant bits all 0 s in advance, therefore, And they all leave them unchanged . Pure result: the bit of the least significant digit is cleared, and the rest of the word remains the same.

To understand why m and -m give the least significant set bit, combine the above with the knowledge that in addition 2s, -x = ~(x-1)