c++ - 从位集中获取某些位的十进制值的快速方法

Question

我有一个变量 mask类型 std::bitset<8>作为

std::string bit_string = "00101100";
std::bitset<8> mask(bit_string);

有没有一种有效的方法可以快速屏蔽掉另一个给定 std::bitset<8> input 的相应(三)位？并将所有那些屏蔽掉的位移到最右边？例如，如果 input是10100101 , 那么我想快速得到 00000101等于 5十进制。那我可以vect[5]快速索引 vect 的第 6 个元素这是std::vector<int>尺寸为 8。

或者更确切地说，我能否快速获得屏蔽位的十进制值(保留它们的相对位置)？或者我不能？

我想在我的例子中可以利用的优势是 bitset<8> mask我有。我应该以某种方式操纵它以快速完成工作。

我是这样看的(由 Spektre 添加):

mask  00101100b 
input 10100101b
---------------
&     ??1?01??b
>>         101b
             5

Answer 1

首先要注意的是:如果您的掩码以二进制形式提供，则您无法避免 O(n) 的复杂性，因为 n 是掩码位数。但是，如果您的掩码对于多个输入是不变的，您可以将掩码预处理为一系列 m 掩码和移位转换，其中 m 小于或等于您的值 1 屏蔽位。如果您在编译时知道掩码，您甚至可以预先构造转换，然后得到您的 O(m)。

要应用这个想法，您需要为掩码中的每组 1 位创建一个子掩码，并将其与移位信息组合。移位信息是通过计算当前组右边零的个数来构建的。

例子:

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

如果将子变换转换为数组，则可以轻松地将它们应用到循环中。