Bitwise Filter

Using Bitwise and to quickly narrow a search space

by _sir

HTML

<header>
  
<h1>
Contains Letters
</h1>
<h2>
Search with Bitwise AND
</h2>
</header>
<main>
<p>
Using bit-masking to assign each letter a single bit, we can quickly calculate the bitmask of a string and use bitwise logic to locate matches.
</p>
<p>
The way I ordered them is earliest letter the least significant bit. So <code>cabbage</code> collapses to <code>abceg</code>, which can be represented in bit order as <code>g_e_cba</code> or <code>1010111</code>, which is <code>87</code> in decimal.
</p>
<p><code>bread</code> is <code>100000000000011011</code> in binary, or <code>131099</code> in decimal. 
</p>
<p>
<code>bread</code> is the same number as <code>beard</code> because it has the same letters.
</p>
<p>
We can take this number as a <em>mask</em> and use <em>bitwise and</em> to compare it to other words. When all the letters match with bitwise and, the output will be the same as the mask.
</p>
<p>
When we apply this, we find all those letters in <code>badger</code> and <code>sideboard</code>, and several more words.
</p>
<p>When working with large datasets or needing high performance code, substituting bitwise operations like this can be very efficient.
</p>
<p>
In our example below, this bitwise operation can quickly cut down our search space from over 2300 entries. A real-world applicaiton could use this as a "first pass" before more complex filtering and sorting.
</p>
<p>
This technique also features in <a href="https://www.youtube.com/watch?v=c33AZBnRHks">a Stand-up Maths video</a> which touches on bitwise performance.
</p>
<section class="code">
<fieldset>
   <legend>
   Search
   </legend>
  <label for="query">Query</label> <input id="query" name="query" type="text" />
  <br />
  <label>Results</label>
<div id="results"></div>
</fieldset>
</section>
</main>

CSS

html,
body {
  font: 1rem/1.4rem sans-serif;
  background-color: #fafaf0;
}

header,
main {
  display: block;
  max-width: 40em;
  margin: 1rem auto;
  padding: 1rem;
  border-radius: 1rem;
  box-shadow: 0 0.4rem 1rem #00000080;
}

header {
  background: #004953;
  color: white;
}

main {
  background: white;
}

main p {
  max-width: 40em;
}

main code {
  background: #ddd;
  padding: 0.2em;
}

.code label {
  display: block;
  margin-top: 1rem;
  padding: 0.25em 0;
  font-weight: bold;
}

.code input {
  border: 1px solid #ccc;
  font-size: 1rem;
  padding: 0.5rem;
}

legend {
  font-size: 1.25rem;
  padding: 0 0.25rem; 
}

#results code {
  margin-right: 1rem;
}

#results code .match {
  font-weight: bold;
  background: #aea;
}

JavaScript

// Original source of nouns: https://gist.github.com/ijmacdowell/8325491
// Some cleanup required
export const maskedValues = [
  [ 673813, 'accelerator' ],
  [ 155917, 'accordion' ],
  [ 1597445, 'account' ],
  [ 1597445, 'accountant' ],
  [ 4750429, 'acknowledgment' ],
  [ 1851653, 'acoustic' ],
  [ 16910597, 'acrylic' ],
  [ 524293, 'act' ],
  [ 549125, 'action' ],
  [ 2621717, 'active' ],
  [ 19398917, 'activity' ],
  [ 671749, 'actor' ],
  [ 917525, 'actress' ],
  [ 688153, 'adapter' ],
  [ 549129, 'addition' ],
  [ 393241, 'address' ],
  [ 1847833, 'adjustment' ],
  [ 1574921, 'adult' ],
  [ 2629721, 'advantage' ],
  [ 3027225, 'advertisement' ],
  [ 2097437, 'advice' ],
  [ 795105, 'afghanistan' ],
  [ 131365, 'africa' ],
  [ 659633, 'aftermath' ],
  [ 679985, 'afternoon' ],
  [ 3014833, 'aftershave' ],
  [ 1720561, 'afterthought' ],
  [ 81, 'age' ],
  [ 8281, 'agenda' ],
  [ 667729, 'agreement' ],
  [ 131329, 'air' ],
  [ 1442051, 'airbus' ],
  [ 137473, 'airmail' ],
  [ 174353, 'airplane' ],
  [ 704769, 'airport' ],
  [ 426369, 'airship' ],
  [ 137217, 'alarm' ],
  [ 935939, 'albatross' ],
  [ 18565, 'alcohol' ],
  [ 133203, 'algebra' ],
  [ 133457, 'algeria' ],
  [ 2307, 'alibi' ],
  [ 16779281, 'alley' ],
  [ 674113, 'alligator' ],
  [ 16795649, 'alloy' ],
  [ 14341, 'almanac' ],
  [ 559251, 'alphabet' ],
  [ 542721, 'alto' ],
  [ 1063169, 'aluminium' ],
  [ 1063169, 'aluminum' ],
  [ 1062935, 'ambulance' ],
  [ 135445, 'america' ],
  [ 1601537, 'amount' ],
  [ 1847313, 'amusement' ],
  [ 17330177, 'anatomy' ],
  [ 813521, 'anethesiologist' ],
  [ 139345, 'anger' ],
  [ 10321, 'angle' ],
  [ 155713, 'angora' ],
  [ 14593, 'animal' ],
  [ 12561, 'anime' ],
  [ 11281, 'ankle' ],
  [ 4595729, 'answer' ],
  [ 532481, 'ant' ],
  [ 663813, 'antarctica' ],
  [ 663569, 'anteater' ],
  [ 583697, 'antelope' ],
  [ 17326209, 'anthony' ],
  [ 17492161, 'anthropology' ],
  [ 700433, 'apartment' ],
  [ 16828481, 'apology' ],
  [ 1998849, 'apparatus' ],
  [ 165905,...