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

Question

我有一个 std::bitset<8> 类型的变量 mask as

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

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

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

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

我是这样看的（由 Spektre 添加）：

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

Answer 1

我是这样看的：

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

我会通过从 LSB 扫描位为掩码中的每个设置位创建一个位权重 table 并为设置位添加权重 1,2,4,8,16... 并为其余位留零所以：

      MSB           LSB
--------------------------
mask   0 0 1 0 1 1 0 0 bin
--------------------------
weight 0 0 4 0 2 1 0 0 dec (A)
input  1 0 1 0 0 1 0 1 bin (B)
--------------------------
(A.B) 0*1+0*0+4*1+0*0+2*0+1*1+0*0+0*1 // this is dot product ...
              4     +     1 
--------------------------
                     5 dec                 
--------------------------

抱歉，我根本不在 Python 中编写代码，所以没有代码......我仍然认为直接使用整数类型会更好，但这可能只是我的低级 C++ 想法......

Answer 2

首先要做的事情是：如果您的掩码以二进制形式提供，则您无法避免 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 3

您的域足够小，您可以对其进行暴力破解。平凡地，unsigned char LUT[256][256] 可以在 64 KB 中存储所有可能的结果。

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

通过意识到最高掩码是 11100000 可以进一步减小大小，但您可以只测试掩码的最低位。当掩码是偶数时，f(input, mask) == f((input&mask)/2, mask/2)。最高的 odd mask 仅为 11000001 或 191。这会进一步降低您的 LUT，至 [192][192].

一种更 space 高效的算法将 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;

这表明您需要另一个 table, 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 字节，但我怀疑这不值得。

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

Fast way to get the decimal value of certain bits from a bitset

c++

algorithm

bit-manipulation

bitset