在C/C++中快速比较特定的咬点的方法

Question

我有一个面具和一个号码。掩码由值为0xf的咬口和包含我必须比较的比特组成的咬口组成。0xf的意思是“这些位元在比较时不相关”。示例：

1111 1111 0011 1111 (Mask)
xxxx xxxx 0010 xxxx (Number)
Result: Not Equal since 3dec != 2dec


1111 1111 0011 1111 (Mask)
xxxx xxxx 0011 xxxx (Number)
Result: Equal since 3dec == 3dec

相关咬口的位置可能在口罩内的任何位置。示例：

0110 1111 1111 1111 (Mask)
0110 xxxx xxxx xxxx (Number)
Result: Equal since 6dec == 6dec

我玩~，^，等等，但我找不到一个简单的方法来得到一个“真”或“假”。是否有任何解决方案不移动或比较每咬一口？

Answer 1

正如其他人所指出的，您实际上没有一个掩码；您有一个想要比较的nybbles向量，而nybb0Xf的意思是“不关心”。因此，第一步是找出要比较和忽略什么的实际掩码：

uint64_t dont_care = ((mask & 0x7777777777777777ULL) + 0x1111111111111111ULL) & mask;
dont_care &= 0x8888888888888888ULL;
dont_care |= dont_care >> 1;
dont_care |= dont_care >> 2;

这将计算一个真正的掩码--如果dont_care为0xf，则mask的每个nybble将为0xf，否则为0。请注意，对于每个mask值，只需要执行一次。它还假定64位(16 nybble)掩码--较小的掩码可以使用较小的类型/常量。

现在，您可以简单地测试掩码：

if ((number | dont_care) == mask) { ...

计算dont_care的另一种方法是：

uint64_t dont_care = mask & (mask << 1);
dont_care &= dont_care << 2;
dont_care &= 0x8888888888888888ULL;
dont_care |= dont_care >> 1;
dont_care |= dont_care >> 2;

这在某些机器上可能更快(使用较少的大常数，但在某些CPU上使用更多的移位，这在某些CPU上是缓慢的)。如果你真的关心，你可以分析这两种方法，看看哪一种对你的机器来说更快。

还有另一种可能性：

uint64_t dont_care = mask & (mask >> 1);
dont_care &= dont_care >> 2;
dont_care &= 0x1111111111111111ULL;
dont_care *= 15;

Answer 2

我认为问题的出现是因为你的面具不是真正的面具。它既是面具又是“旗帜”。如果你把这些分开..。

0000 0000 1111 0000 (Mask)
0000 0000 0011 0000 (Flag)
xxxx xxxx 0010 xxxx (Number)

那么数学就变得超级容易了！

if (Number&Mask == Flag) 

​

我怀疑是否有办法做到这一点，而不需要一次比较一次，使用0xF作为一个特殊标志使所有标准操作对您来说都是无用的。

​

​

我想，至少我应该想出一个有用的表达方式，即使它违反了“一次咬一口”的部分。

​

if (((Mask&0xF000)!=0xF000 && (Mask&0xF000)!=(Number&0xF000)) ||
    ((Mask&0x0F00)!=0x0F00 && (Mask&0x0F00)!=(Number&0x0F00)) ||
    ((Mask&0x00F0)!=0x00F0 && (Mask&0x00F0)!=(Number&0x00F0)) ||
    ((Mask&0x00F0)!=0x000F && (Mask&0x000F)!=(Number&0x000F)))
{
    std::cout << "fail\n";
} else {
    std::cout << "pass\n";
}

http://coliru.stacked-crooked.com/a/8317f68c396802e0

我不认为这是最快的方法，但至少它是准确的，而且应该相当快，因为这些操作都是快速和独立的，并且有几个副本，任何半体面的优化器都应该注意到。

Answer 3

对于每一个数字，

• 它的值可以是要传递的任何东西(您用“x”表示)。
• 它的值必须是0才能传递(您用“0”表示)。
• 它的值必须是1才能传递(你用“1”表示)。

在这个数字中，每一位需要超过一位信息。

这通常是使用与您的数字一样大的两个数字来完成的。一个是面具，另一个是期望的值。

如果你想检查一下

xxxx xxxx 0010 xxxx

你需要

mask = 0x00F0;
flag = 0x0020;

( num & mask ) == flag

从技术上讲，因为您总是比较4位，所以您可以用比num更少的位来编码您想要的信息。

data = 1 << 4 | 0x2;  // 1 is the nibble offset, 0x2 is the flag.

shift = ( data >> 4 ) * 4;
mask = 0xF << shift;
flag = ( data & 0xF ) << shift;

( num & mask ) == flag