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

This is a code challenge. I came across this question on SO about testing if a number is included in a given set. The typical solution would be:

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

However, I'm wondering if a solution using bitmask exists to this problem? Can someone fill in CREATE_BITMASK and JUDGEMENT in below?

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

where givenSet consists of arbitrary positive integer that fits into Int32.

My instant observation is that, if x equals n in the given set, then we can apply XOR to obtain x ^ n === 0. And 0 is a special number that we might be able to leverage. But I don't have further idea.

For your reference, here's the Bitwise Operator Laws

Update: Pointed out by @coderLMN, the above form might be misleading.

Basically I'm seeking a one-pass solution, without the need to iterate through each element in the given set.

What I'm really asking is if it's possible to encode the requirement (the given set) into one single data structure (most likely a bitmask).

A valid solution can take any form, as long as it doesn't need to iterate over the given set for each individual test. Don't limit yourself.

javascriptbitmaskphpcssemail


Solution 1:[1]

Theoretically, It's impossible.

Suppose you got a set of CREATE_BITMASK, BITWISE_OP and JUDGEMENT that worked for all the integers in givenSet, so you must have:

(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

Given the requirement that the integers fits into Int32, bitmask has to be the same format, which means no matter whatever the BITWISE_OP is, it's not possible to have it operate on different integers to get a same result.

Solution 2:[2]

This should do it:

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

Quote from 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

Solution 3:[3]

Keep in mind that this can be different depending on the client and clients change a lot. for example I had issues similar to what you are facing from the outlook from ios and on windows and other clients too. You have to test and build your html to work in multiple outdated IE based engines.

I suggest you test your code in one of the tools listed in this question: Testing HTML email rendering

I used https://email2go.io/home to fix my layouts.

Hope it helped.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 coderLMN
Solution 2 Mårten Wikström
Solution 3 Ricardo Silva

Related Questions