Example implementations relate to records based on bit-shifting. For example, a computing device may include at least one processor to receive a query, create a normalized query, and generate a mapping of the normalized query for each record in a set of records in a database using a state array, the mapping being based on bit-shifting of bits associated with similarities between each character in the normalized query and each character in a field of the respective record in the set of records, each successive level of the state array indicating a stronger match between the query and the respective record than an immediately prior level in the state array. The processor may calculate a score associated with each record based on the respective mapping and may provide a subset of the set of records in response to the query based on the score associated with each record.