c++ - 在C++中检测匹配位

例如，我正在尝试使用两个bitset对象

a = 10010111
b = 01110010

并从两个变量中删除位(如果它们在相同的位置/索引中匹配)。所以我们将留给

a = 100xx1x1 = 10011
b = 011xx0x0 = 01100

有什么办法可以做到这一点？

最佳答案

其他答案显示了不错的，惯用的C++方法。不幸的是，它们将变得很慢。即使是AndyG's clever template-based solution，尽管它在编译时做了尽可能多的工作，但仍使编译器生成许多必须在运行时执行的代码。

如果您关心速度并针对支持BMI2 instruction set的处理器(可能是Intel Haswell和更高版本，或者是AMD Excavator和更高版本)，则可以使用执行 PEXT instruction的a parallel bit extraction。这使您可以在大约两台机器指令中从字面上解决整个问题。

由于您不是用汇编语言编写的，因此可以对PEXT指令使用相应的内在函数，即 _pext_u32 。在基本形式上，该代码简单，易读且非常高效:

#include <stdint.h>      // for uint32_t
#include <x86intrin.h>   // for _pext_u32()  [on MSVC, drop the 'x86']

void RemoveMatchingBits(uint32_t& a, uint32_t& b)
{
   const uint32_t mask = (a ^ b);
   a = _pext_u32(a, mask);
   b = _pext_u32(b, mask);
}

首先，您将两个值(a和b一起)按位异或。这将生成一个掩码，如果在a或b中设置了相应的位，则将设置掩码中的每个位，否则不设置该位。然后将此掩码用作_pext_u32进行位提取的基础。两种位提取操作都使用相同的掩码，因此仅需要一条XOR指令。每个_pext_u32内部函数都将编译为PEXT指令。因此，除了一些MOV指令可在值周围乱码(这将取决于用于生成代码的编译器以及此代码是否内联)之外，仅需要三个机器代码指令。这是当代版本的GCC和Clang编译上述功能的方式(MSVC和ICC发出极其相似的代码):

RemoveMatchingBits(unsigned int&, unsigned int&):
    mov     eax, DWORD PTR [rdi]    // rdi contains a pointer to 'a'
    mov     edx, DWORD PTR [rsi]    // rsi contains a pointer to 'b'
    xor     edx, eax
    pext    eax, eax, edx
    mov     DWORD PTR [rdi], eax
    mov     eax, DWORD PTR [rsi]
    pext    eax, eax, edx
    mov     DWORD PTR [rsi], eax
    ret

如您所见，这里的大多数额外指令都是MOV，它是根据我们编写函数以按引用接受其参数并就地修改这些值的方式来强制执行的。调整函数的编写方式，和/或通过使优化器在调用站点内联它，将产生更有效的实现。

如果要使用std::bitset，只需稍作修改即可。 to_ulong()成员函数允许您访问原始位以进行操作。就像是:

void RemoveMatchingBits(std::bitset<8>& a, std::bitset<8>& b)
{
   const std::bitset<8> mask = (a ^ b);
   a = _pext_u32(static_cast<uint32_t>(a.to_ulong()), static_cast<uint32_t>(mask.to_ulong()));
   b = _pext_u32(static_cast<uint32_t>(b.to_ulong()), static_cast<uint32_t>(mask.to_ulong()));
}

注意，鉴于需要处理std::bitset对象，这进一步降低了生成代码的效率。特别是，to_ulong()成员函数必须在溢出的情况下检测并引发异常，即使std::bitset<8>可能无法溢出32位整数类型，MSVC似乎也无法优化该检查。哦，对了，代码会足够快，而且没有人说抽象是完全免费的。

如果您不能假设BMI2支持就进行编译，则可以在运行时使用 CPUID instruction进行检查(实际上，所有x86编译器都为此提供了内在功能)。

如果它不可用，则您的目标不是x86，或者只是不想担心运行时委派的复杂性，那么您可以使用另一种位困惑的实现方式。具体来说，您想要的是“压缩”操作。关于此问题的讨论和代码在小亨利·沃伦(Henry S. Warren)的经典著作Hacker's Delight的第7–4节中给出。

这是“压缩”的一个简单的基于循环的实现，它改编自Hacker's Delight中的图7–9:

uint32_t compress(uint32_t value, uint32_t mask)
{
   uint32_t result = 0;
   uint32_t shift  = 0;
   uint32_t maskBit;
   do
   {
        maskBit = (mask & 1);
        result |= ((value & maskBit) << shift);
        shift  += maskBit;
        value >>= 1;
        mask  >>= 1;
    } while (mask != 0);
    return result;
}

这可以充分模拟PEXT指令，但是速度并不快。以下代码实现了相同的算法，但是在Hacker's Delight中基于图7-10使用了更快的“并行后缀”方法:

uint32_t fallback_pext_u32(uint32_t value, uint32_t mask)
{
   const int log2BitSize = 5;                     // log_2 of the bit size (here, 32 bits)

   value &= mask;                                 // clear irrelevant bits
   uint32_t mk = (~mask << 1);                    // we will count 0's to the right
   uint32_t mp;
   uint32_t mv;
   uint32_t t;
   for (int i = 0; i < log2BitSize; ++i)
   {
      mp     = mk ^ (mk <<  1);                   // parallel suffix
      mp     = mp ^ (mp <<  2);
      mp     = mp ^ (mp <<  4);
      mp     = mp ^ (mp <<  8);
      mp     = mp ^ (mp << 16);
      mv     = (mp & mask);                       // bits to move
      mask   = ((mask ^ mv) | (mv >> (1 << i)));  // compress mask
      t      = (value & mv);
      value  = ((value ^ t) | (t >> (1 << i)));   // compress value
      mk    &= ~mp;
   }
   return value;
}

此后备实现比单个PEXT指令要慢，但是它完全是无分支的，因此在处理随机输入时，不会对错误预测的分支有任何隐藏的惩罚。您应该在这里从CPU中获得最大可能的吞吐量，但是无论哪种方式，它肯定比带有一系列条件分支的for循环快得多，如其他答案所建议。

关于c++ - 在C++中检测匹配位，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41720249/