Memory inside a computer is split apart into individual machine words, with primitive operations like addition, subtraction, and multiplication taking constant time. This means that, if we can pack multiple pieces of data into a single machine word, we can essentially get a limited form of parallel computation. Through a variety of very clever tricks, we can use this to speed up searching and sorting.
This first lecture explores word-level parallelism through a data structure for very small integers and a technique for computing most-significant bits in time $O(1)\text.$ It will lay the groundwork we'll use next time when exploring fusion trees.
Links