用于测试元素是否包含在有限集中的位掩码解决方案？

Question

这是一个代码挑战。我在 SO 上遇到了关于测试给定集合中是否包含数字的问题。典型的解决方案是：

const givenSet = [9, 91, 20, 18, 17, 37]
function isIncluded(x) {
  return givenSet.includes(x)
}

但是，我想知道是否存在使用位掩码的解决方案来解决这个问题？有人可以在下面填写 CREATE_BITMASK 和 JUDGEMENT 吗？

const givenSet = [9, 91, 20, 18, 17, 37]
const bitmask = CREATE_BITMASK(givenSet)
function isIncluded(x) {
  return JUDGEMENT(x, bitmask)
}

其中 givenSet 由适合 Int32.

的任意正整数组成

我的即时观察是，如果给定集合中的 x 等于 n，那么我们可以应用 XOR 来获得 x ^ n === 0。 0 是一个我们可以利用的特殊数字。但我没有进一步的想法。

这里是Bitwise Operator Laws

供您参考

更新：@coderLMN 指出，上述表格可能会产生误导。

基本上我正在寻找一种一次性解决方案，不需要遍历给定集合中的每个元素。

我真正想问的是，是否可以将需求（给定的集合）编码为一个单一的数据结构（很可能是位掩码）。

一个有效的解决方案可以采用任何形式，只要它不需要为每个单独的测试迭代给定的集合。不要限制自己。

Answer 1

理论上是不可能的。

假设您有一组 CREATE_BITMASK、BITWISE_OP 和 JUDGEMENT，它们适用于 givenSet 中的所有整数，那么您必须有：

(9  BITWISE_OP bitmask) === JUDGEMENT
(91 BITWISE_OP bitmask) === JUDGEMENT
(20 BITWISE_OP bitmask) === JUDGEMENT
(18 BITWISE_OP bitmask) === JUDGEMENT
(17 BITWISE_OP bitmask) === JUDGEMENT
(37 BITWISE_OP bitmask) === JUDGEMENT

鉴于整数符合 Int32 的要求，bitmask 必须是相同的格式，这意味着无论 BITWISE_OP 是什么，都不可能拥有它对不同的整数进行运算以获得相同的结果。

Answer 2

如果正整数的范围在合理的最大值内并且重复值不是一个因素，那么可以使用类型化数组（例如，Uint32Array），该数组中的位索引表示一个整数值。

例如，如果设置了第 12 位，则数字 12 是您设置的一部分。如果位 320 已设置（即 Uint32Array 中第 10 个元素的 0 位），则数字 320 是该集合的一部分。这样就可以直接通过索引数组来判断一个数是否是集合的一部分，而不是扫描数组。

下面的代码包含一个 class，它在给定最大整数值的情况下定义了一个表示一组整数的位数组。方法 setBit 在集合中添加或删除一个整数，方法 getBit 确定一个整数是否在整数集合中。

class BitArray {

  constructor( maxN ) {
    this.max = maxN;
    this.bitArray = new Uint32Array( ( maxN / 32 |0 ) + 1 );
  }
  
  getBit( n ) {
    if ( 0 <= n && n <= this.max ) {
      return 0 < ( this.bitArray[ n / 32 |0 ] & ( 1 << ( n % 32 ) ) );
    }
    return NaN;
  }
  
  setBit( n, val ) {
    if ( 0 <= n && n <= this.max ) {
      if ( val ) {
        this.bitArray[ n / 32 |0] |=  1 << ( n % 32 );
      } else {
        this.bitArray[ n / 32 |0 ] &=  ~( 1 << ( n % 32 ) );
      }
    }    
  }
  
}

let ints = new BitArray( 100 );
[9, 91, 20, 18, 17, 37].forEach( n => ints.setBit( n, true ) );


console.log( `5: ${ ints.getBit( 5 ) }` );
console.log( `37: ${ ints.getBit( 37 ) }` );
console.log( `91: ${ ints.getBit( 91 ) }` );
console.log( `500: ${ ints.getBit( 500 ) }` );

编辑整数集中具有大整数的稀疏数组

作为对一些关于内存使用的评论的跟进，一个解决方案是进行两层查找，第一层实现为稀疏数组。第一层是一个数组，其中 returns 整数块中的整数数量和对第二层的引用，即原始答案中提到的位图数组。

举例来说，假设第一层按 15 位的块映射整数，即每个块 2^15 或 32768 个整数。第一层由索引为 0...131071 的对象数组组成，元素初始化为 emtpy / undefined。一旦在第一层元素的范围内设置了位，那么 tier1 就成为一个对象，其中 count 指示块中设置的位数，并引用跟踪整数集的第二层位图数组在 tier1 范围内。由于32768 / 32（每个Uint32的位数）是1024，那么第二层位图是一个Uint32Array(1024)，足以表示一个32768个整数的块。

一般来说，人们希望跟踪大量整数（否则线性搜索可能会更快），但举例来说，假设要跟踪的整数是...

[ 0, 1, 2, 1000000, 1000000000 ]

...在这种情况下，第一层和第二层的表示将是...

tier1[ 0 ] = { count: 3, tier2: [ 7, 0, 0, ..., 0 ] }   // Range 0 - 32767
tier1[ 1 ] = undefined                                  // Range 32768 - 65535
tier1[ 2 ] = undefined                                  // Range 65536 - 98304
        o
        o
        o
tier1[ 29 ] = undefined                                           // Range 950272 - 983039
tier1[ 30 ] = { count: 1, tier2: [ 0, 0, 0, ..., 512, ..., 0 ] }  // Range 983040 - 1015807
tier1[ 31 ] = undefined                                           // Range 1015808 - 1048575

        o
        o
        o
tier1[ 30516 ] = undefined                                          // Range 999948288 - 999981055
tier1[ 30517 ] = { count: 1, tier2: [ 0, 0, 0, ..., 32 ..., 0 ] }   // Range 999981056 - 1000013823
tier1[ 30518 ] = undefined                                          // Range 1000013824 - 1000046591
        o
        o
        o
tier1[ 131071 ] = undefined                                         // Range 4294934528 - 4294967295

现在，要确定特定整数是否是整个集合的一部分，只需计算 tier1 索引即可，如果没有未定义，则查看 tier2 位图。

举例来说，当寻找 1000000 时，tier1 索引由 1000000 / 32768（每个块有 32768 个整数）计算，舍入到索引 30。然后 [=18] 的关联 tier1[ 30 ] 位索引=] 寻找 1000000 - 983040 或位 16960，并返回该位值（在这种情况下它将是 true）。

这仍然通过计算两层索引提供对集合中整数的直接访问（无需扫描数组），并适应稀疏整数集，特别是因为第 1 层数组将利用 JavaScript内置稀疏数组功能...

请注意，可以调整块的大小（在此示例中为 32768 个整数）以适应数据的预期分布和密度，以平衡内存利用率。

Answer 3

应该这样做：

const CREATE_BITMASK = x => new Set(x);
const JUDGEMENT = (x,s) => s.has(x);

引自MDN：

In particular, it is, on average, faster than the Array.prototype.includes method when an Array object has a length equal to a Set object's size

用于测试元素是否包含在有限集中的位掩码解决方案？

A bitmask solution to test if an element is included in a finite set?

javascript

bitmask