I have a variable mask of type std::bitset<8> as
std::string bit_string = "00101100";
std::bitset<8> mask(bit_string);
Is there an efficient way to quickly mask out the corresponding (three) bits of another given std::bitset<8> input and move all those masked out bits to the rightmost? E.g., if input is 10100101, then I would like to quickly get 00000101 which equals 5 in decimal. Then I can vect[5] to quickly index the 6th element of vect which is std::vector<int> of size 8.
Or rather, can I quickly get the decimal value of the masked out bits (with their relative positions retained)? Or I can't?
I guess in my case the advantage that can be taken is the bitset<8> mask I have. And I'm supposed to manipulate it somehow to do the work fast.
I see it like this (added by Spektre):
mask 00101100b
input 10100101b
---------------
& ??1?01??b
>> 101b
5
First things first: you can't avoid O(n) complexity with n being the number of mask bits if your mask is available as binary. However, if your mask is constant for multiple inputs, you can preprocess the mask into a series of m mask&shift transformations where m is less or equal to your number of value 1 mask bits. If you know the mask at compile time, you can even preconstruct the transformations and then you get your O(m).
To apply this idea, you need to create a sub-mask for each group of 1 bits in your mask and combine it with a shift information. The shift information is constructed by counting the number of zeroes to the right of the current group.
Example:
mask = 00101100b
// first group of ones
submask1 = 00001100b
// number of zeroes to the right of the group
subshift1 = 2
submask2 = 00100000b
subshift2 = 3
// Apply:
input = 10100101b
transformed = (input & submask1) >> subshift1 // = 00000001b
transformed = (input & submask2) >> subshift2 // = 00000100b
+ transformed // = 00000101b
If you make the sub-transforms into an array, you can easily apply them in a loop.