时间戳

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

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

问题描述

这是一个代码挑战。我在 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是一个我们可以利用的特殊数字。但我没有进一步的想法。

供您参考，这是按位运算符法则

更新：@coderLMN 指出，上述形式可能具有误导性。

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

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

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

标签： javascriptbitmask

解决方案

理论上，这是不可能的。

假设你有一组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是什么，都不可能让它对不同的整数进行操作以获得相同的结果。

推荐阅读