从bitset获取某些位的十进制值的快速方法

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

如果将子变换转换为数组,则可以轻松地将它们应用于循环中.

Answer 2

您的域名足够小,您可以强制执行此操作.简单地说,一个unsigned char LUT[256][256]可以存储所有可能的结果只有64 KB.

我知道掩码最多有3位,因此您可以将该维度中的查找表大小限制为[224].而且因为f(input, mask) == f(input&mask, mask)事实上你可以减少LUT unsigned char[224][224].

通过实现最高掩模可以进一步减小尺寸,11100000但您可以测试掩模的最低位.当面具是均匀的时候f(input, mask) == f((input&mask)/2, mask/2).最高的奇数掩码仅为11000001或者是191.这会进一步降低你的LUT [192][192].

更节省空间的算法分割input和mask分成2个半字节(4位).你现在有一个非常简单的LUT[16][16]查找高低部分:

int himask = mask >> 4, lomask = mask & 0xF;
int hiinp = input >> 4, loinp = input & 0xF;
unsigned char hiout = LUT[himask][hiinp];
unsigned char loout = LUT[lomask][loinp];
return hiout << bitsIn[lomask] | loout;

这表明你需要另一张桌子char bitsIn[15].

举个例子:

mask  0010 1100b 
input 1010 0101b

himask = 0010
hiinp  = 1010
hiout  = 0001
lomask = 1100
loinp  = 0101
loout  = 0001
bitsIn[lowmask 1100] = 2
return (0001 << 2) | (0001)

请注意,这很容易推广到超过8位:

int bitsSoFar = 0;
int retval = 0;
while(mask) { // Until we've looked up all bits.
   int mask4 = mask & 0xF;
   int input4 = input & 0xF;
   retval |= LUT[mask4][input4] << bitsSoFar;
   bitsSoFar += bitsIn[mask4];
   mask >>= 4;
   input >>= 4;
}

由于这个LUT只能保存半字节,你可以将其减少到16*16/2字节,但我怀疑这不值得.