Editing Trie (section)

=== Bitwise tries ===
{{see also| x-fast trie| Bitwise trie with bitmap}}
Bitwise tries are used to address the enormous space requirement for the trie nodes in a naive simple pointer vector implementations. Each character in the string key set is represented via individual bits, which are used to traverse the trie over a string key. The implementations for these types of trie use [[SIMD|vectorized]] CPU instructions to [[find first set|find the first set bit]] in a fixed-length key input (e.g. [[GNU Compiler Collection|GCC]]'s <code>__builtin_clz()</code> [[intrinsic function]]). Accordingly, the set bit is used to index the first item, or child node, in the 32- or 64-entry based bitwise tree. Search then proceeds by testing each subsequent bit in the key.<ref name="willar83">{{cite journal|title=Log-logarithmic worst-case range queries are possible in space O(n)|doi=10.1016/0020-0190(83)90075-3|url=https://www.sciencedirect.com/science/article/abs/pii/0020019083900753|volume=17|issue=2|date=27 January 1983|pages=81–84|first=Dan E.|last=Willar|journal=Information Processing Letters}}</ref>

This procedure is also [[Locality of reference|cache-local]] and [[Parallel programming model|highly parallelizable]] due to [[CPU register|register]] independency, and thus performant on [[out-of-order execution]] CPUs.<ref name="willar83" />