Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / Javascript
Tip/Trick

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

Rate me:
Please Sign up or sign in to vote.
5.00/5 (4 votes)
12 Aug 2011CPOL3 min read 31.6K   2   3
How to use javascript bitwise operations to filter out search results based on user selected filters in checkboxes
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Web Developer
Greece Greece
I am a web developer for a software house in Athens, Greece. I currently work almost exclusively with the Microsoft stack of languages, and most prominently with C#. However, I have worked extensively with PHP in the past, dabbled in C and C++ while doing my MSc, and for my pet projects I usually resort to Python, if a GUI is not necessary. That said, I'm also usually the guy that oversees/designs the database schema for each new project at work.

When not in front of the computer, I enjoy watching and helping my two young daughters grow up. Sometimes I do that while in front of the computer too.

Comments and Discussions

 
GeneralReason for my vote of 5 Good tip, thanks. Pin
Dr.Walt Fair, PE13-Aug-11 6:09
professionalDr.Walt Fair, PE13-Aug-11 6:09 
GeneralReason for my vote of 5 nice one Pin
Monjurul Habib27-Jul-11 22:17
professionalMonjurul Habib27-Jul-11 22:17 
GeneralReason for my vote of 5 This is a very clear presentation of... Pin
George Tryfonas26-Jul-11 22:51
George Tryfonas26-Jul-11 22:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.