Using bitwise operations to filter results based on user selected filters in javascript

Time and again, I have encountered the same problem: There is a large list of items, each with a list of true/false options (e.g. list of hotels, each with true/false options for having a pool, having wi-fi access, accepting credit card payments etc), and it is required that the user browsing the site at hand be able to filter out some of these items based on personal preferences. Taking the example of the hotels, one might wish to check for hotels that have wi-fi access and a hairdresser, but they do not care if the hotel offers a pool.

Typically, the user interface for these options is a (long?) list of checkboxes, each representing a particular option. For the example of the hotels, a following list could exist:

<ul>
    <li><input type="checkbox" name="opt_pool" id="opt_pool" /><label for="opt_pool">swimming pool</label> </li>
    <li><input type="checkbox" name="opt_bar" id="opt_bar" /><label for="opt_bar">bar</label> </li>
    <li><input type="checkbox" name="opt_restaurant" id="opt_restaurant" /><label for="opt_restaurant">restaurant</label> </li>
    <li><input type="checkbox" name="opt_wifi" id="opt_wifi" /><label for="opt_wifi">wi-fi hotspot</label> </li>
    <li><input type="checkbox" name="opt_shuttle" id="opt_shuttle" /><label for="opt_shuttle">shuttle service to the nearest beach</label> </li>
</ul>

If a user checks the first three checkboxes, the system should return only those hotels that have a pool, a bar and a restaurant.

The problem at hand is how to encode this information in a quick and concise way.

What is usually required, is that boxes that are left unchecked are irrelevant, meaning that the user is not interested whether the selected option exists or not in the results (e.g. the user is not interested if there is a wi-fi hotspot). A checked checkbox means that the user is interested to see only those items that implement the option (i.e. only those hotels that have a swimming pool).

Since these are all true/false options, and I assume that there won't be more than 32 options available, it makes sense to somehow collect them together (i.e. create a bitfield). This is relatively easy:

<ul>
    <li><input type="checkbox" name="opt_pool" id="opt_pool" value="0" /><label for="opt_pool">swimming pool</label> </li>
    <li><input type="checkbox" name="opt_bar" id="opt_bar" value="1" /><label for="opt_bar">bar</label> </li>
    <li><input type="checkbox" name="opt_restaurant" id="opt_restaurant" value="2" /><label for="opt_restaurant">restaurant</label> </li>
    <li><input type="checkbox" name="opt_wifi" id="opt_wifi" value="3" /><label for="opt_wifi">wi-fi hotspot</label> </li>
    <li><input type="checkbox" name="opt_shuttle" id="opt_shuttle" value="4" /><label for="opt_shuttle">shuttle service to the nearest beach</label> </li>
</ul>

<script type="text/javascript">
    var selectedOptions=0;
    selectedOptions+=document.getElementById("opt_pool").checked ? 1 << parseInt(document.getElementById("opt_pool").value) : 0
    selectedOptions+=document.getElementById("opt_bar").checked ? 1 << parseInt(document.getElementById("opt_bar").value) : 0
    selectedOptions += document.getElementById("opt_restaurant").checked ? 1 << parseInt(document.getElementById("opt_restaurant").value) : 0
    selectedOptions += document.getElementById("opt_wifi").checked ? 1 << parseInt(document.getElementById("opt_wifi").value) : 0
    selectedOptions += document.getElementById("opt_shuttle").checked ? 1 << parseInt(document.getElementById("opt_shuttle").value) : 0

</script>

We've made two changes. First, we added a value to each element, and secondly, we've added a javascript block to create our bitfield.

Thus comes our first encounter with bitwise operators in javascript. In particular, the << operator is the left-shift operator. A fun "property" of this operator is that in essence it doubles the number it acts on (for sufficiently small numbers) each time it acts on it. So, in the above code
parseInt(document.getElementById("opt_pool").value is 0, therefore 1<<0=1 (no shift). Similarly, parseInt(document.getElementById("opt_bar").value is 1, therefore 1<<1=2 and
parseInt(document.getElementById("opt_restaurant").value is 2, therefore 1<<2=4 etc.

Eventually, we end up with a number between 0 and 2^(number_of_options)-1 inclusive. The edge values account for no checkboxes selected (0) and all boxes selected (2^(number_of_options)-1). This will be our bitfield.

Now, each item in our list should also have a bitfield, wherein each option it implements (or doesn't implement) is encoded in the exact same way. Let's assume the following list:

    var AllHotels=[
        {name:"Hotel 1", options: 22},
        {name:"Hotel 2", options: 13},
        {name:"Hotel 3", options: 9},
        {name:"Hotel 4", options: 30},
        {name:"Hotel 5", options: 31},
        {name:"Hotel 6", options: 5},
        {name:"Hotel 7", options: 10},
        {name:"Hotel 8", options: 15},
        {name:"Hotel 9", options: 21},
        {name:"Hotel 10", options: 23},
        {name:"Hotel 11", options: 31}
];

The above list could have come from an AJAX JSON call, or any other way.

Now comes the tricky part. We need to include the items that have set the same bits as the request bitfield or more - like I said, the user needs to see only the hotels that offer a pool, but doesn't care if there is a shuttle service to the beach, so the first bit of all included results should be set, but the last bit is irrelevant so both set and unset values are good. In essence, for each bit in the bitfield, we require the following truth table:

Offered    Required    Result
   1          1          1
   1          0          1
   0          1          0
   0          0          1

The above result is achieved if we invert the value of the "required" bit and then apply a bitwise or operator between the two. In javascript, this is (~Required)|Offered.So, noting that for a hit, the result will be all 1's, and a 32-bit signed number of all 1's is actually -1, our javascript code becomes

<script type="text/javascript">
    var selectedOptions=0;
    selectedOptions+=document.getElementById("opt_pool").checked ? 1 << parseInt(document.getElementById("opt_pool").value) : 0
    selectedOptions+=document.getElementById("opt_bar").checked ? 1 << parseInt(document.getElementById("opt_bar").value) : 0
    selectedOptions += document.getElementById("opt_restaurant").checked ? 1 << parseInt(document.getElementById("opt_restaurant").value : 0
    selectedOptions += document.getElementById("opt_wifi").checked ? 1 << parseInt(document.getElementById("opt_wifi").value) : 0
    selectedOptions += document.getElementById("opt_shuttle").checked ? 1 << parseInt(document.getElementById("opt_shuttle").value) : 0

var FilteredHotels=[];
for(var i=0;i<allhotels.length;++i)>
{
    if (((~selectedOptions)|allHotels[i].options)==-1)
    {
        FilteredHotels.push(allHotels[i]);
    }
}
</script>

The FilteredHotels array now contains the filtered results. For our example, where the user has asked for a pool, a bar and a restaurant, the request bitfield will be selectedOptions=7 and the filtered hotels will be

    FilteredHotels=[
        {name:"Hotel 5", options: 31},
        {name:"Hotel 8", options: 15},
        {name:"Hotel 10", options: 23},
        {name:"Hotel 11", options: 31}
];

As noted, this is not restricted to hotels, but to any type of list of objects containing a true/false list of options.