2

我想知道是否有一种方法可以使用按位运算符屏蔽 int 值列表，并使用该掩码来了解 int 值是否是掩码中的值之一。

即，如果我有值 129 和 17，如何计算一个掩码，告诉我掩码中是否有一个 int 值对应（如果 int 值是 129 或 17）。

我希望通过下一个伪代码更好地理解我的问题。

* *编辑：我想仅在一个值（掩码）中打包、屏蔽或“压缩”一个 int 数组，然后只接受要屏蔽的值列表中的值（数组）。

可能吗？提前致谢。

valuesToMask = [17, 129, ...]
mask = getmask(valuesToMask)
lstValues = [0,1, 10, ..., 17, 18, 19, ..., 129, ...]
foreach(int value, in lstValues) {
    if(check(mask,value)) 
       printf("\nValue %d is in the mask", value);
    else 
       printf("\nValue %d is not in the mask", value);
}

提前致谢。我非常感谢您的帮助和您的时间。

（对不起我的英语不好）

4

3 回答 3

2

您可以使用Bloom Filters部分解决您的问题。其工作方式是，为了测试一组项目中的成员资格，您定义散列函数以将每个项目映射到一个位键。对于元素的插入，将过滤器的位设置在位置...等于1。对于元素的查找，如果您在任何...处检测到零位，则保证不在集合中。然而，根据 N、M 和 K 的值，您得到误报的可能性很小（即您没有从散列函数中检测到零，但之前没有存储在过滤器中）。NKMah1(a)hk(a)bh1(b)hk(b)bb

在伪代码中：

const int M = 256;
typedef std::bitset<M> Mask;

int listValues[N] = { v1, ... , vN };
typedef unsigned char (*)(int) HashFunction; // maps int to 0...255
HashFunction hash[K] = { h1, ..., hK };

Mask make_mask(int x)
{
    Mask m(0):
    for (int i = 0; i < K; ++i) { 
        m[(hash[i])(x)] = 1; // update mask with item's hash
    }
    return(m);
}    

// initialize
Mask BloomFilter(0);
for (int i = 0; i < N; ++i) {        
    BloomFilter |= make_mask(listValues[i]);
}

// probe
bool is_not_in_filter(const Mask& F, int x)
{
    // if a zero-bit in F matches a 1-bit in make_mask(x), then x is not in F
    return ~F & make_mask(x) != 0; 
}

// call
int x = ...;
bool in_set = is_not_in_filter(BloomFilter, x);

实际上，这会将每个项目扩展为一个 M 位密钥，并且过滤器是所有项目的聚合按位或。然后，对集合成员的测试变成了一个简单的（尽管是概率的）在 NEGATED 过滤器与要测试的 M 位扩展项之间的按位与。

更新： 上面的代码是伪代码来解释它是如何工作的。要获得一个实际的库，请参见例如实验性的Boost.Bloomfilters或bloom

于 2012-05-04T12:55:42.100 回答
2

您可以对某些值集执行此操作，但通常不一定如此。例如，如果您想确定一个值是 4、5、6 还是 7，那么您可以执行以下操作：

if ((value & ~3) == 4) ...

这将创建一个掩码，除最低有效两位外，所有位都为 1。运算符有效地将&最低有效两位设置为 0。然后，比较会检查位模式是否与您要查找的值匹配。在二进制表示中，这如下所示（假设value是 8 位值）：

value        masked
00000011     00000000 = 0
00000100     00000100 = 4
00000101     00000100 = 4
00000110     00000100 = 4
00000111     00000100 = 4
00001000     00001000 = 8

例如，如果您只想检查“4、5 或 7”，则此技术将不起作用。

于 2012-05-03T23:49:32.250 回答
-1

我想你问如何检查一个数字是 129 还是 17。

int[] lstValues = [0,1, 10, 17, 18, 19, 129];
foreach(int value in lstValues) {
    if(lstValues == 129 || lstValues == 17) 
        printf("\nValue is in the mask");
    else 
        printf("\nValue is not in the mask");
}
于 2012-05-03T23:50:32.263 回答